[Jinx786]

Hi there!
For school project we have to solve mathematical expressions (with big integers) in postfix notation (in number systems from 2 to 16), but since I never worked with this notation I am a little confused as how to do it.
The instructions state that the program has to read on standard input like this:

<radix>
<value_name_1>
<value_1>
<value_name_2>
<value_2>
.
.
.
<value_name_n>
<value_n>
"expression"
<expression>

where expression is like z x * y + z x y + + +

I stopped at the last part, where I read the expression and have to parse it. I have no idea how to do it the correct way. I still have to write methods for +,-,* and / for this project but until I figure out the basics I cant even start. Any input about this problem is greatly appreciated. I have seen some people using stack. How does stack help here? Thanks!

[Dienes]

Stack is useful since it is LIFO and every time you hit an operator when parsing the input, it uses the top two values (i.e. the ones inserted last) for its calculations.

So the basic way of doing it is:

- Parse input string, for every token do:
  - If it is a number
    - Push it to the stack
  - If it is an operator
    - Pop two numbers from the stack
    - Calculate result based on operator
    - Push result back to stack
- Pop final result from stack

[Jinx786]

Hmm, thanks, very useful tip, but what about those operators at the end? Three plusses? What do they represent? Is it correct that
z x * y + z x y + + + parses into (((z * x) + y) + z + x + y)?

I have seen x y * - becoming -x * y in infix. Does that mean that operators at the end mean sign for individual variables, starting at the beginning? Or does that mean that you have to negate the result? :\

[grlira]

Jinx786 posted:

Hmm, thanks, very useful tip, but what about those operators at the end? Three plusses? What do they represent? Is it correct that
z x * y + z x y + + + parses into (((z * x) + y) + z + x + y)?

I have seen x y * - becoming -x * y in infix. Does that mean that operators at the end mean sign for individual variables, starting at the beginning? Or does that mean that you have to negate the result? :\

As far as your last question: no. That has to do with what the expression means.

Let's say you're parsing x y * -
You read x, and push it onto the stack. The stack is now x
You read y and push it onto the stack. The stack is now x|y
You read *. It's an operator. It's a binary operator so you pop two operands from the stack. The stack is now empty.
You calculate the result (x*y) and push it back in. The stack is now (x*y).
You read -. Let's say this symbol represents the unary operation, but not the binary (to avoid ambiguity). This is an unary operator, so you pop one element from the stack (and indeed that is all you can do. A binary operator at this point would have to be interpreted as a syntax error). The stack is now empty.
You calculate the result -(x*y) and push it back in. The stack is now -(x*y).
No more tokes on input, and one value on the stack means you've reached the end of a successful parse. You pop the final result: -(x*y)

Now note that -(x*y) is the same as -x*y = x*(-y) = x*y*(-1), etc, etc. This doesn't mean that a - at the end of the expression negates the first value. It just happens that, because of the way multiplication works, those two expressions are equivalent.

[Jinx786]

Oh, yes, that makes sense, thanks :D