Evaluation of Prefix and Postfix Expressions using stack – DSA Course playlist in C++

🔧 Evaluation Methods by Notation:

Notation	Evaluation Method	Needs Stack?
Infix	Convert using precedence rules	❌ (uses parsing trees, not stack)
Postfix	Left to right using a stack	✅ Yes
Prefix	Right to left using a stack	✅ Yes

For Postfix and Prefix evaluation, a stack is typically used.

✅ 1. Evaluation of Postfix Expression

Postfix = Operators come after operands
👉 Scan left to right, use stack

✍️ Example: 5 3 2 * +

Step-by-step:

1. Push 5 → Stack: [5]
2. Push 3 → Stack: [5, 3]
3. Push 2 → Stack: [5, 3, 2]
4. * → Pop 3 & 2 → 3 * 2 = 6 → Push 6 → Stack: [5, 6]
5. + → Pop 5 & 6 → 5 + 6 = 11 → Push 11

✅ Final Answer: 11

✅ 2. Evaluation of Prefix Expression

Prefix = Operators come before operands
👉 Scan right to left, use stack

✍️ Example: + 5 * 3 2

Step-by-step:

1. Start from right: Push 2, 3 → Stack: [2, 3]
2. * → Pop 3 and 2 → 3 * 2 = 6 → Push 6 → Stack: [6]
3. Push 5 → Stack: [6, 5]
4. + → Pop 5 and 6 → 5 + 6 = 11 → Push 11

✅ Final Answer: 11

✅ 3. Evaluation of Infix Expression

Infix = Operators between operands (e.g. 5 + 3 * 2)
👉 Needs operator precedence and parentheses

✍️ Example: 5 + 3 * 2

Steps:

1. Recognize precedence: * comes before +
2. Compute 3 * 2 = 6
3. Then 5 + 6 = 11

✅ Final Answer: 11

📊 Summary

Expression	Type	Evaluation Method	Result
5 + 3 * 2	Infix	Use precedence	11
+ 5 * 3 2	Prefix	Right to left stack	11
5 3 2 * +	Postfix	Left to right stack	11

✅ Can Machines Use Infix for Evaluation?

❌ Not directly.

Machines do not evaluate infix expressions directly — they first convert them into a form that is easier to process, such as postfix, prefix, or an abstract syntax tree (AST).

🧠 Why Not Infix?

Because infix expressions:

• Depend on operator precedence (e.g., * before +)
• Require parentheses to clarify order
• Are ambiguous without a full grammar and parsing

These factors make infix hard to evaluate directly in a linear or stack-based way.

🔄 What Do Machines Do Instead?

1. Parse the infix expression using grammar rules and precedence
2. Build an Abstract Syntax Tree (AST) or convert to postfix/prefix
3. Evaluate the result using:
   • A stack (postfix/prefix), or
   • Tree traversal (AST-based)

✅ Can Machines Use both Prefix and Postfix for Evaluation?

Yes — machines can evaluate both prefix and postfix.

But postfix is more commonly used in stack-based evaluation models, especially in practical implementations like compilers, interpreters, and virtual machines.

🔄 Postfix vs. Prefix in Machines

Feature	Postfix (RPN)	Prefix (Polish Notation)
Evaluation Order	Left to right	Right to left
Needs Stack?	Yes	Yes
Ease of Evaluation	Simpler for stack-based machines	Slightly trickier (right-to-left parsing)
Common Usage	Widely used (e.g., JVM bytecode, calculators)	Rarely used in real systems

🔧 Why Do Machines Prefer Postfix?

• Postfix works naturally with LIFO (stack):
  • You push operands.
  • When you encounter an operator, you pop the top two operands, evaluate, and push the result.
• Simple left-to-right scan → perfect for interpreters.

🧠 Prefix is Valid — Just Less Used

Machines can evaluate prefix:

• Just requires scanning right to left
• Still needs a stack
• Less natural for left-to-right interpreters and compilers

✅ Summary

Question	Answer
Can machines only use postfix?	❌ No — they can use prefix too
Why is postfix preferred?	✔ Easier left-to-right evaluation with a stack
Is prefix used in real-world systems?	❌ Rarely — mostly theoretical or academic