Convert infix to postfix
Updated
Shunting-yard: operands go straight to output. Operators go on a stack, popped to output when a new operator has precedence ≤ the top (for left-assoc), or at a closer. '(' is pushed; ')' pops until '('.
What to focus on
"2+3*4" → 2 3 4 * +. "(2+3)*4" → 2 3 + 4 *. The stack holds operators only, not numbers.
Worked examples
precedence
s = "2+3*4"- * binds tighter
- output 2 3 4 * +
Result: 2 3 4 * +
parens
s = "(2+3)*4"- + comes out at )
- then *
Result: 2 3 + 4 *
left assoc
s = "8-3-1"- first - pops before second
- 8 3 - 1 -
Result: 8 3 - 1 -
Try it
Write infixToPostfix(s). s is well-formed infix of single-digit integers, + − *, and matching parentheses. Operands go to output. Operators go on a stack. Numbers never enter that stack. Return the postfix tokens. "2+3*4" → 2 3 4 * +. "(2+3)*4" → 2 3 + 4 *. "8-3-1" → 8 3 - 1 -.
s is well-formed infix of single-digit integers, + − *, and matching parentheses. Operators are left-associative.