S
Anbei der gleiche Code aber mit printfs, um die Rekursion besser verstehen zu können:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *get_padding(char *buffer, int rl, int tree)
{
int i;
buffer[0] = 0;
if(tree)
{
strcat(buffer, "+-");
for(i = 0; i < rl; ++i)
strcat(buffer, "-");
} else {
strcat(buffer, "| ");
for(i = 0; i < rl; ++i)
strcat(buffer, " ");
}
return buffer;
}
// rl == recursion level, helps to debug it
double fnord(double v, int rl) {
char padding[1024*10]; // should be enough
char *tmp_padding = get_padding(padding, 2*rl+2, 0);
int c = getchar();
printf("%s fnord() initial value: %lf\n", tmp_padding, v);
if(c >= '0' && c <= '9') {
double res;
printf("%s fnord() reads '%c'. Get next digits\n", tmp_padding, c);
res = fnord(v*10 + (c - '0'), rl+1);
printf("%s fnord() got and returns '%lf'\n", tmp_padding, res);
return res;
}
printf("%s fnord() reads '%c', not a digit.\n", tmp_padding, c);
printf("%s fnord() puts it back in stdin and returns the inital value %lf\n", tmp_padding, v);
ungetc(c, stdin);
return v;
}
// rl == recursion level, helps to debug it
double calc(int rl) {
char padding[1024*10]; // should be enough
double tmp = 0.0;
double operand;
double res;
printf("%s calc() recursion level: %d\n", get_padding(padding, 2*rl, 1), rl);
int c = getchar();
char *tmp_padding = get_padding(padding, 2*rl+2, 0);
if(c == '+' || c == '-' || c == '/' || c == '*')
{
printf("%s operator %c: requires 2 operand, calc() will be executed twice\n", tmp_padding, c);
tmp = calc(rl+1);
printf("%s first operand: tmp = %lf --> stack.pop()\n", tmp_padding, tmp);
operand = calc(rl+1);
printf("%s second operand: tmp = %lf --> stack.pop()\n", tmp_padding, operand);
if(c == '+') res = tmp + operand;
if(c == '-') res = tmp - operand;
if(c == '/') res = tmp / operand;
if(c == '*') res = tmp * operand;
printf("%s intermediate result %lf %c %lf = %lf\n", tmp_padding, tmp, c, operand, res);
printf("%s calc returns %lf --> stack.push(%lf)\n\n", tmp_padding, res, res);
return res;
}
if(c >= '0' && c <= '9')
{
printf("%s number %c: fnord will get next operand\n", tmp_padding, c);
res = fnord(c - '0', rl+1);
printf("%s fnord returns operand %lf --> stack.push(%lf)\n", tmp_padding, res, res);
return res;
}
if(c == EOF) {
fprintf(stderr, "Unexpected end of input\n");
exit(-1);
}
printf("%s c='%c' (%d): no rule for this character, ignore it and resume\n", tmp_padding, c, c);
return calc(rl+1); /* skip things we don't understand */
}
/* Aufruf mittels:
* prog.exe < input.txt
*
* Beispiele
* "* 3 + 5 9" = 42
* "+ - * / 1 2 3 4 5" = 2.5
*/
int main(void) {
printf("Result = %f\n", calc(0));
return 0;
}
Die Ausgabe ist recht lang, also mach dein Terminal sehr lang und am besten eine kleine Schrift, damit die Zeilen nicht umgebrochen werden.
Fange mit kleinen Beispielen an wie "+ 10 26" und dann komplexre wie "+ 3 * 5 125"
Beispiel
$ echo "+ 10 20" | ./prefix_calculator
+- calc() recursion level: 0
| operator +: requires 2 operand, calc() will be executed twice
+--- calc() recursion level: 1
| c=' ' (32): no rule for this character, ignore it and resume
+----- calc() recursion level: 2
| number 1: fnord will get next operand
| fnord() initial value: 1.000000
| fnord() reads '0'. Get next digits
| fnord() initial value: 10.000000
| fnord() reads ' ', not a digit.
| fnord() puts it back in stdin and returns the inital value 10.000000
| fnord() got and returns '10.000000'
| fnord returns operand 10.000000 --> stack.push(10.000000)
| first operand: tmp = 10.000000 --> stack.pop()
+--- calc() recursion level: 1
| c=' ' (32): no rule for this character, ignore it and resume
+----- calc() recursion level: 2
| number 2: fnord will get next operand
| fnord() initial value: 2.000000
| fnord() reads '0'. Get next digits
| fnord() initial value: 20.000000
| fnord() reads '
', not a digit.
| fnord() puts it back in stdin and returns the inital value 20.000000
| fnord() got and returns '20.000000'
| fnord returns operand 20.000000 --> stack.push(20.000000)
| second operand: tmp = 20.000000 --> stack.pop()
| intermediate result 10.000000 + 20.000000 = 30.000000
| calc returns 30.000000 --> stack.push(30.000000)
Result = 30.000000
