Recursive Prefix Expression [Problem]

So I have been stuck on this program. Here it is for reference:

Code:

#include <stdio.h> #include <stdlib.h> int main(){ int c; c = getchar(); printf("%d\n", prefix(0, -1, -1, c)); return 0; } int prefix(int op, int a, int b, int c){ int x = 0; printf("%c, %d, %d, %c\n", op, a, b, c); // Check if char is a operator if(c == '+' || c == '-' || c == '*' || c == '/') op = c; //Parse integers if(c > 47 && c < 58){ if(c == 48) c = 0; if(c == 49) c = 1; if(c == 50) c = 2; if(c == 51) c = 3; if(c == 52) c = 4; if(c == 53) c = 5; if(c == 54) c = 6; if(c == 55) c = 7; if(c ==56) c = 8; if(c == 57) c = 9; if(a == -1) a = c; else{ b = c; } } if(c == '\n') return a; if(a >= 0 && b >= 0){ if(op == '+'){ x = b; b = -1; return a + x; } if(op == '-'){ x = b; b = -1; return a - x; } if(op == '*'){ x = b; b = -1; return a * x; } if(op == '/'){ x = b; b = -1; return a / x; } } if(b == -1) return prefix(op, a, b, c = getchar()); exit(1); }

The idea is the program needs to read in an expression from input and evaluate it. The case I am currently working on is "++3 4 3" = 10. I have +3 4 working (it equates to 7). I am not allowed to use built in functions besides that ones I used already or any structs. The idea is to do this recursively, but my problem is after evaluating +3 4 I can't get it to the next step which would be +7 3. Does anyone have any suggestions for how to set up the recursion so the stack variables can be evaluated properly?

essentially the idea is
f(0) = +, -1, -1
f(1) = +, -1, -1
f(2) = +, 3, -1
f(3) = +, 3, 4 = 7
f(2) = +, 7, 3, = 10
f(1) = , 10, -1
f(0) = , 10, -1
main prints 10

So I want to change my b value from -1 to some valid number if a is not null
and I want to change my operator after every evaluation.

A recursive Polish notation calculator? Weird.

Why haven't you enabled warnings for your compiler? You've forgotten the function declaration; all variables and functions need to be declared or defined before they're used.

What is your logic?

Prefix notation, as defined using Backus-Naur form, is

Code:

<expression> ::= <value> <value> ::= <number> | <operator> <value> <value>

In other words, each value is either a number, or an operator followed by two values.

As this is a recursive definition, it is very easy to implement recursively.

If you consider the expression + + 3 4 3, the first operator is + and its values are + 3 4 and 3 . Note that value + 3 4 is composed of an operator + and values 3 and 4. Thus, the entire expression is equal to + 7 3 which is equal to 10.

My recursive prefix() function would be quite simple; it would simply return the numeric value of next <value> in the Backus-Naur definition above, using recursion. In pseudocode:

Code:

function prefix(no parameters), returns a number: Read 'token'. If 'token' is a number, return its value as a number. 'token' must be an arithmetic operator. If it is not, the expression is invalid, and you should abort. Do a recursive call to this function, saving the result to 'firstnumber'. Do another recursive call to this function, saving the result to 'secondnumber'. Apply the arithmetic operator 'token' to the two numbers 'firstnumber' and 'secondnumber', and return the resulting numeric value.

Remember those old HP calculators back in the day when HP was an innovative company? If you can believe this, back in the 1980s HP had a series of programmable calculators that used reverse polish notation, ie they had a stack and used postfix operators.

The language was similiar to Forth, or other concatenative languages. It was quite innovative and frankly much easier to program then the current crop of calculators we use. (I'm getting to a solution for you hold on..)

Stack languages had some notable advantages and may still be in use in astronomy and some of our robotic spacecraft. One of the big advantages was how compactly you build the control logic for the interpreter. Little to no operand decoding and very concise code itself. Great for boot loaders to. Anyway I digress.

Sooo let's take your example of a binary infix operators. Say you want to do something like,
* + 3 1 4 which should parse to something like (3+1)*4. That's confusing right? If you knew lisp you'd get (* (+ 3 1) 4), which makes it clearer, but if you were working in a postfix language you would have,

3 1 + 4 * , 3 and 1 get pushed on to the stack in succession, the stack looks like [3,1], with 1 on top. After the + you apply the binary function and replace the two elements at the top with it's one result [4] . You then take the 4 and get [4, 4] after pushing the new 4 to the top. After the * you would get [16], your answer.

Easy peasy and simple to implement right? The stack could be a simple array with an index that points to the top. Incrementing the index and writing to that position is a push, decrementing it is a pop. Applying an operation uses the top 2 positions as the inputs, you write the output to the 2nd position and decrement the index.

Now for the fun part. Your prefix language has a 1-1 mapping to a postfix representation.
To get there consider pushing your operands (+-, * etc) on to an operand stack, and numbers into a number stack. Whenever your number stack gets 2 or more numbers it's time to pull the last operator out of your operator stack.

This is just one approach, there are others. Another good approach would be to create a binary syntax tree. Once the children are evaluated the parent, which is marked by the operand can be evaluated. This is often used in functional languages.

Have fun and good luck!

btw it's better not to use "magic numbers". Apart from making the code less readable, not all computers use the ASCII representation for characters.

So instead of:

Code:

if(c > 47 && c < 58)

The following immediately makes the intent clear without the need to comment and is cross platform:

Code:

if(c >= '0' && c <= '9')

And because the C Standard guarantees that the representation of the numbers is contiguous you can convert from the character representation to its corresponding integer value with:

Code:

my_char = my_char - '0';

so if my_char is initially e.g. '9' ( or even its ASCII representation on an ASCII machine ), then the above would return 9.

That would save you having to write all those if statements.

Thanks, guys. Unfortunately, I ran out of time before the first post was made, so I ended up not getting the optimal code. So lesson learned, I need to leave more time if I'm going to ask for clarifications from now on, and this is all great stuff to apply to future code.