richard chuquilin

Greenhorn

Posts: 6

posted 3 years ago

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

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

posted 3 years ago

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

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