Stack

Infix to Prefix

What is Prefix Notation?

Prefix notation, also called Polish notation, puts the operator in front of its operands instead of between them.

That means the familiar 3 + 4 turns into + 3 4 once written in prefix form. Since the operator always leads, there's no need for parentheses to sort out which operation happens first.

Infix to Prefix Conversion Steps

Reverse the infix expression, while keeping the positions of parentheses correct.
Replace ( with ) and vice-versa.
Convert the reversed expression to postfix using a stack.
Finally, reverse the postfix expression to get the prefix expression.

How Does It Work?

Take (A + B) * (C - D). The whole pipeline runs top to bottom — the amber brackets in row 2 are the ones that had to be flipped when the expression was reversed:

Step 3 is the only part that needs a stack. Here it is one token at a time, scanning the reversed expression ( D - C ) * ( B + A ):

1. Scan '(' — '(' is pushed onto the stack

2. Scan 'D' — 'D' is an operand, so it goes straight to the output

3. Scan '-' — Push '-' onto the stack

4. Scan 'C' — 'C' is an operand, so it goes straight to the output

5. Scan ')' — Pop operators to the output until '(' is found

6. Scan '*' — Push '*' onto the stack

7. Scan '(' — '(' is pushed onto the stack

8. Scan 'B' — 'B' is an operand, so it goes straight to the output

9. Scan '+' — Push '+' onto the stack

10. Scan 'A' — 'A' is an operand, so it goes straight to the output

11. Scan ')' — Pop operators to the output until '(' is found

12. End of scan — Scan finished — pop everything left on the stack

Token being scanned / bracket flippedOn the stack / not yet scannedWritten to the output

That leaves the postfix form D C - B A + *, and reversing it once more gives the prefix answer * + A B - C D.

Operator Precedence Table

Operator	Meaning	Precedence
( )	Parentheses	Highest
^ %	Exponentiation / Modulus	2
* /	Multiplication / Division	3
+ -	Addition / Subtraction	4 (Lowest)

Note: Higher precedence means the operation will happen first. Exponentiation (^) is evaluated right-to-left, while others are left-to-right.

Daily DSA Challenge by Scale Engineer

Test Your Knowledge before moving forward!

Stack Quiz Challenge

How it works:

+1 point for each correct answer
0 points for wrong answers
-0.5 point penalty for viewing explanations
Earn stars based on your final score (max 5 stars)

PreFix implementation using Stack

// Prefix Evaluation using Stack (JavaScript)
function evaluatePrefix(expression) {
  let stack = [];
  // Process expression in reverse order
  for (let i = expression.length - 1; i >= 0; i--) {
    const char = expression[i];
    if (!isNaN(char)) {
      stack.push(parseInt(char));
    } else {
      const a = stack.pop();
      const b = stack.pop();
      
      switch(char) {
        case '+': stack.push(a + b); break;
        case '-': stack.push(a - b); break;
        case '*': stack.push(a * b); break;
        case '/': stack.push(Math.floor(a / b)); break;
      }
    }
  }
  return stack.pop();
}

// Example: "+*235" becomes (2*3)+5 = 11
console.log(evaluatePrefix("+*235")); // Output: 11

Done With the Learning

Mark Polish : prefix as done and view it on your dashboard