C++ Calculator using Stacks and Queues

Question

I'm trying to understand a topic in class about using stacks and queues as a means of programming a calculator. I understand what infix and postfix expression is but how does it make it easier for a program to evaluate an expression and why are queues and stacks ideal in this situation? Thanks

Answer 1

It makes the order of operations simpler to handle, for example:

+ * - 4 2 5 3

Can only mean

((4 - 2) * 5) + 3

Which might be more readable for us, but we need to know the order of operations and match parentheses to figure it out.

As for implementing: if you had a stack, you could handle the expression above as follows:

1. Read + (an operation), push it onto the stack,
2. Read * (an operation), push it onto the stack,
3. Read - (an operation), push it onto the stack,
4. Read 4 (a number), the top of the stack is not a number, so push it onto the stack.
5. Read 2 (a number), the top of the stack is a number, so pop from the stack twice, you get 4 - 2, calculate it (2), and push the result (2) onto the stack.
6. Read 5 (a number), the top of the stack is a number, so pop from the stack twice, you get 2 * 5, push the result (10) onto the stack.
7. Read 3 (a number), the top of the stack is a number, so pop from the stack twice, you get 3 + 10, push the result (13) onto the stack.
8. Nothing left to read, pop from the stack and return the result (13).

So as you can see, the expression was evaluated using a few simple rules and without having to search through the entire string for parentheses or having to decide whether multiplication has priority over addition and subtraction.