Java: Evaluate postfix expression

Question

This is a theoretical one:

I have to evaluate an expression which I already have transformed from infix to postfix. The postfix is saved inside a Queue, since I wanted to avoid working with a String. This way I know where are the divisions between numbers and I can access it in the "right" order.

It looks like this:

// Original expression: 2+(3+1)-(5-3)^2*3-1
Queue: [2.0, 3.0, 1.0, +, +, 5.0, 3.0, -, 2.0, ^, 3.0, *, -,1.0, -]

Now I thought using two stacks:

origin stack (which has been filled up with the queue contents beforehand)
and destination stack

passing the postfix expression from one to the other, at the same time asking whether the current element is a number o an operator and counting the consecutive numbers.

If I reach an operator and the number count is at least 2 I'll do the operation and push it onto the destination stack. Reaching the end of the origin stack (empty now) I would pass everything back to it and start all over until there would be only the result left.

I am asking me now:

Is this a good approach or should I rather try to detect all patterns of the type NumberNumberOperator and process them in one go?
And if the second option is the way to go, how could this be done?

Sounds complicated. Why not just one stack for numbers. If you read a number from your queue, push it on the stack. If you read an operator, pop its operands off the stack, do the operation, push the result back on. If the operands aren't there, then throw an exception. — Solomon Slow
– Solomon Slow, Commented Apr 8, 2014 at 17:06

user207421 · Accepted Answer · 2014-04-08 17:28:48Z

1

No. You only need one stack, and when you're done there is nothing left to 'start all over' with.

When you dequeue a number, push it: when you dequeue an operator, pop two values, evaluate the operator with those two operands, and push the result. When you reach the end of the input there should be exactly one value in the stack, the result. Otherwise the input was ill-formed.

answered Apr 8, 2014 at 17:28

user207421

312k45 gold badges324 silver badges493 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Java: Evaluate postfix expression

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related