Stack And Arithmetic Evaluation

Question

A stack is said to be the ideal data structure for Arithmetic Evaluation. Why is it so?
Why do we even need a data structure for Arithmetic Evaluation? I've been studying about this for some time now and still confused. I don't understand what is the use of Prefix and Postfix expressions because the Infix expression is quite readable.

Answer 1

Answer for the part of why postfix/prefix over infix is quite well explained here.As a summary infix is readable but not easily parsed
As for why stack is used here is:
1: push,pop in O(1) time are quite useful for evaluation.
2: push: add the operand on stack.
3: pop: remove the operand and evaluate expression(binary) 4: final result is the only one left on stack after parsing

Answer 2

The infix expression is readable, yes. But if you want to write an algorithm that can evaluate an arithmetic expression, how would you do?

Take the following expression:

3 + 4 * 5 + 2 ^ 3 * 12 + 6

How does your algorithm proceed from there?

A simple and naive way is to look for the highest-precedence operation, evaluate it, then rewrite the string, and keep doing that until all operations have been performed. You'd get this result:

3 + 4 * 5 + 2 ^ 3 * 12 + 6
3 + 4 * 5 + 8 * 12 + 6
3 + 20 + 96 + 6
23 + 102
125

That is one way to do it. But not a particularly efficient way. Looking through the string for the highest-precedence operation takes time linear in the length of the string, and you have to do that once per operation, and rewrite the string every time. You end up with something like a quadratic complexity. There might be a few tricks to be slightly more efficient, but it's not going to be as efficient as other existing methods.

Another possible method is to put the expression into a tree, called a "syntax tree" or "abstract syntax tree". We get this:

        +
 /   /    \   \
3   *      *   6
   / \    / \
  4   5  ^   12
        / \
       2   3

This tree is easier to evaluate for an algorithm, compared to the expression we had before: it is a linked structure, in which you can easily replace one branch by the value of that branch without having to rewrite everything else in the tree. So you replace 2^3 with 8 in the tree, then 8 * 12 with 96, etc.

Postfix (or prefix) notation is harder to read for humans, but much easier to manipulate for an algorithm. My previous example becomes this in postfix:

3 4 5 * + 2 3 ^ 12 * + 6 +

This can be evaluated easily reading it from left to right; every time you encounter a number, push it onto a stack; every time you encounter an operator, pop the two numbers on top of the stack, perform the operation, and push the result.

Assuming the postfix expression was correct, there should be a single number in the stack at the end of the evaluation.

EXPR  | [3] 4 5 * + 2 3 ^ 12 * + 6 +
STACK | 3

EXPR   | 3 [4] 5 * + 2 3 ^ 12 * + 6 +
STACK  | 3 4

EXPR   | 3 4 [5] * + 2 3 ^ 12 * + 6 +
STACK  | 3 4 5

EXPR   | 3 4 5 [*] + 2 3 ^ 12 * + 6 +
STACK  | 3 20

EXPR   | 3 4 5 * [+] 2 3 ^ 12 * + 6 +
STACK  | 23

EXPR   | 3 4 5 * + [2] 3 ^ 12 * + 6 +
STACK  | 23 2

EXPR   | 3 4 5 * + 2 [3] ^ 12 * + 6 +
STACK  | 23 2 3

EXPR   | 3 4 5 * + 2 3 [^] 12 * + 6 +
STACK  | 23 8

EXPR   | 3 4 5 * + 2 3 ^ [12] * + 6 +
STACK  | 23 8 12

EXPR   | 3 4 5 * + 2 3 ^ 12 [*] + 6 +
STACK  | 23 96

EXPR   | 3 4 5 * + 2 3 ^ 12 * [+] 6 +
STACK  | 119

EXPR   | 3 4 5 * + 2 3 ^ 12 * + [6] +
STACK  | 119 6

EXPR   | 3 4 5 * + 2 3 ^ 12 * + 6 [+]
STACK  | 125

And there we have the result. We only had to read through the expression once. Thus the execution time is linear. This is much better than the quadratic execution time we had when trying to evaluate the infix expression directly and had to read through it several time, looking for the next operation to perform.

Note that converting from infix to postfix can also be done in linear time, using the so-called Shunting Yard algorithm, which uses two stacks. Stacks are awesome!