programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# stacks post fixed math

richard chuquilin
Greenhorn
Posts: 6
I need help with this post fixed math. I want that when I do something like this: 2 3 5 + * I want first to add 3 and 5 and then multiply by 2 = 16. But instead it does 5*3+2=17

Jesper de Jong
Java Cowboy
Sheriff
Posts: 16060
88
Your implementation to evaluate RPN (Reverse Polish Notation) expressions looks more complicated than necessary.

You don't need to check the precedence of operations, and you don't need a stack for operations; you only need a stack for the values.

The algorithm for evaluating an RPN expression is very simple:

- Loop through all tokens
-- If the current token is a value: push it on the stack
-- If the current token is an operation: pull two numbers off the stack, perform the operation on these numbers, push the result value on the stack
- At the end there should be exactly one value on the stack; that's the final result.

Look at what happens if you evaluate, for example: 2 3 5 + *

- push 2 on the stack; the stack now looks like: [2]
- push 3 on the stack; the stack now looks like: [2 3]
- push 5 on the stack; the stack now looks like: [2 3 5]
- pull 5 and 3 from the stack, add them and push the result; the stack now looks like: [2 8]
- pull 8 and 2 from the stack, multiplu them and push the result; the stack now looks like: [16]

So, get rid of the precedence method and the stack for operations.

Piet Souris
Master Rancher
Posts: 2044
75
hi Richard,

as you describe yourself, it looks like the operators are reversed.
Indeed, the type of your 'operations' is a stack. Now, for the numbers,
that's okay, but for the operators you should use a queue.
I also do not understand what the method 'precedence' is for.
In this post fix math (is that the same as Reversed Polish Notation?)
the order of the operators is simply left to right.

It may be easier implemented by using just one stack. if you read
in a number, push it, if you read in an operator, pop the two operands
and push the result, go to the next input, et cetera.

Greetings,
Piet

richard chuquilin
Greenhorn
Posts: 6
• 1
Thank You guys I did a whole new code with basically half the amount of this one and it works great.