Using stacks to do math

 Expressions in math can be ambiguous. Every few months, something like “6/(2+1)*2” goes viral on Twitter, and half the population says “I’m a math professor and the answer is 6” and the other half says “I have 4 math degrees and the answer is 1.”

We are now equipped to solve the problem with Postfix Notation, which takes all that ambiguity out and always produces the correct answer, using a Stack.

Before we look at Postfix, let’s look at Infix. We all know Infix, it’s just very uncommon to see it called that—it’s the expression above. When we have “the sum of a and b”, then that’s written as “a + b” with “a” and “b” surrounding the “+” operator, and so on. As written, “the sum of a and b” looks like Prefix, since “the sum of” comes before the arguments “a” and “b”. Naturally, then, Postfix is where we would see something (in plain English) as “a and b added together,” where a and b come first, and only after you have enough operands do you give the operation.

In Postfix, push onto a stack, until you have enough operators and operands that an operation is legal, pop them off, do the computation, and push the result back.

Let’s take as an example 2 + (3 + 4 + 5 * (6 - 7)), which has some of the same parenthetical ambiguities as the problems that go viral. This is equivalent (just adding some parentheses) to 2 + ((3 + 4) + (5 * (6 - 7))).

In Postfix, that looks like 2 3 4 + 5 6 7 - * + +.

Let’s now use a stack, tracking every operation:

Token	Operation	Stack State
2	Push 2	[2]
3	Push 3	[2, 3]
4	Push 4	[2, 3, 4]
+	Pop 4 and 3 (the top 2 numbers, since + takes 2 arguments), push 3+4=7	[2, 7]
5	Push 5	[2, 7, 5]
6	Push 6	[2, 7, 5, 6]
7	Push 7	[2, 7, 5, 6, 7]
-	Pop 7 and 6 (the top 2 numbers, since - takes 2 arguments), push 6-7=-1	[2, 7, 5, -1]
*	Pop -1 and 5 (the top 2 numbers since * takes 2 arguments), push 5×(-1)=-5	[2, 7, -5]
+	Pop -5 and 7, push 7+(-5)=2	[2, 2]
+	Pop 2 and 2, push 2+2=4	[4]

We’ve gotten to the end of the string, and we have nothing else to process, so the final answer on the stack is the correct answer.

Let’s go back to the fully-parenthesized infix and solve it, just to be sure.

2 + ((3 + 4) + (5 * (6 - 7)))  

1. The innermost parentheses are 6-7 = -1
2. Multiply that by 5 = -5
3. At the same level, we now have 2 additions: 3+4, and {that result}, plus our -5
4. 3 + 4 is 7
5. 7 - 5 is 2
6. Now we’ve cleared all the parentheses, and the result of all that was 2
7. The last step is to add 2 to the result of the parentheses, which is 4
8. Now we’ve cleared the whole expression, so the final answer is 4

 Come up with some relatively simple expressions in traditional infix, and do 3 things:

1. Convert to postfix
2. Use a stack to solve the postfix expression, stepping through with a table as shown above
3. Solve the expression in infix to validate the answer and show to yourself that the methods are equivalent