0
$\begingroup$

I'm trying to understand arithmetic using stacks. Specifically converting infix notation to postfix notation. My question is how you convert an expression like: 1 + (2 + 3) + (4 + 5) that computes in the exact order that the order of operations says.

Meaning: 1 + (2 + 3) + (4 + 5) becomes 1 + 5 + (4 + 5) then 1 + 5 + 9 then 6 + 9

If you do:

Push 1, Push 2, Push 3, Add, Push 4, Push 5, Add

Where Add pops the top two operands off the stack, adds them, and then pushes the sum back on the stack.

Alternative notation: 1 2 3 + 4 5 +

How do you add 1 + (sum of 2 and 3) next? If you do another Add then the sum of 2 and 3 will be added to sum of 4 and 5, because these are the top two on the stack. Is it impossible to do it in the exact same order? Doing each parentheses group first left to right then doing the rest of the computation left to right.

$\endgroup$
8
  • $\begingroup$ Push 1, Push 2, Push 3, Add, Add ? $\endgroup$ – Yuval Filmus Jun 1 '20 at 10:23
  • $\begingroup$ Thanks for responding. But that is 1 + (2 + 3) right? You haven't done (4 + 5) before 1 + (2 + 3) like order of operations from left to right would dictate. I understand you can get the same final sum but I was curious if you can do the computation exactly the same in postfix as infix everytime. $\endgroup$ – user100752 Jun 1 '20 at 16:27
  • $\begingroup$ I don't think it's possible without uses other instructions that affect the stack. The reason is that you're using "ternary plus". Try converting your original expression to incorporate only binary plus. $\endgroup$ – Yuval Filmus Jun 1 '20 at 16:53
  • $\begingroup$ Sorry what is ternary plus? Again thanks for the response. $\endgroup$ – user100752 Jun 1 '20 at 19:51
  • $\begingroup$ It's the function that takes $a,b,c$ to $a+b+c$. Binary plus takes $a,b$ to $a+b$. $\endgroup$ – Yuval Filmus Jun 1 '20 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.