Handle operator precedence with a stack
Updated
While the stack top is an operator of precedence ≥ the incoming operator (left-associative), pop it to output. Then push the incoming. '(' has lowest effective precedence as a stopper so you do not pop it for a '+'.
What to focus on
* and / beat + and -. Equal precedence pops (left assoc). Right-assoc would wait. Most arithmetic in these problems is left-assoc.
Worked examples
incoming + vs *
s = "2*3+4", incoming +- top is *
- * ≥ + so pop *
- then push +
Result: output already has *
incoming * vs +
s = "2+3*4", incoming *- top is +
- + < * so do not pop
- push *
Result: * sits above +
paren stopper
s = "(2+3)*4", incoming * after )- ( was popped by )
- * sees empty or previous
Result: * not blocked by +
Try it
Write shouldPop(top, incoming). top is the operator currently on the stack. incoming is the new operator. Pop while top precedence ≥ incoming (left-associative). '(' does not pop for '+'. Then push incoming. At each operator of "2*3+4", incoming + pops *. At "2+3*4", incoming * does not pop +. '(' blocks pops until ')'.
top and incoming are operators (+, −, *, or '('). Left-associative.