Tulasi Nepali Learning Platform
tulasinepali.com.np • Official Educational & Exam Preparation Notes
1. Overview & Definition (परिचय तथा परिभाषा)
In computer science, an infix expression is the usual way humans write arithmetic expressions, e.g., A + B * C. A postfix expression (also called Reverse Polish Notation, RPN) places the operator after its operands, e.g., A B C * +. Converting infix to postfix is essential for expression evaluation using stacks, compiler design, and many competitive‑exam problems.
2. Core Concepts (मुख्य अवधारणाहरू)
2.1 Operator Precedence and Associativity
- Precedence determines which operator is performed first. Typical order:
^(exponent) >* / %>+ -. - Associativity resolves ties when two operators have the same precedence. Most binary operators are left‑to‑right associative; exponentiation is right‑to‑left.
2.2 Role of the Stack
A stack stores operators temporarily while scanning the infix expression from left to right. The algorithm pushes operators onto the stack and pops them when a lower‑precedence operator or a closing parenthesis is encountered.
2.3 Terminology
- Operand: variable or constant (e.g.,
A,5). - Operator: symbol that performs an operation (
+,*, etc.). - Parentheses:
(and)force grouping.
3. Algorithm Steps (Key Points / Rules / Functions)
- Initialize an empty stack
opStackand an empty output stringpostfix. - Read the infix expression token by token from left to right.
- If the token is an operand, append it to
postfix. - If the token is an ‘(’, push it onto
opStack.- This marks a new sub‑expression.
- If the token is a ‘)’, pop from
opStackand append each popped operator topostfixuntil ‘(’ is encountered. Discard both parentheses. - If the token is an operator (e.g.,
+, -, *, /, ^):- While the stack is not empty and the operator at the top of the stack has higher precedence, or the same precedence with left associativity, pop it and append to
postfix. - Push the current operator onto the stack.
- While the stack is not empty and the operator at the top of the stack has higher precedence, or the same precedence with left associativity, pop it and append to
- After the entire infix string is processed, pop any remaining operators from the stack and append them to
postfix.
The resulting postfix string is the required RPN expression.
4. Comparison Table
| Aspect | Infix Notation | Postfix Notation |
|---|---|---|
| Human readability | High – natural algebraic form | Low – requires learning |
| Evaluation method | Requires precedence parsing or recursion | Simple stack‑based evaluation |
| Parentheses needed | Often required to indicate order | Never required |
| Computer implementation | Complex (shunting‑yard, recursive descent) | Straightforward (single pass) |
5. Practical Application / Real‑World Relevance
- Compilers & Interpreters: Convert source code expressions to postfix (or abstract syntax trees) for efficient code generation.
- Calculator Design: Handheld calculators often use postfix evaluation internally.
- Expression Evaluation in Databases: Query optimizers transform expressions for faster execution.
- Competitive Exams: Loksewa PSC, TSC, and other Nepalese exams frequently ask for infix‑to‑postfix conversion, testing logical reasoning and stack knowledge.
6. Example Walk‑through
Convert the infix expression (A + B) * C - D ^ E ^ F to postfix.
- Initialize:
stack = [],postfix = "" - Read '(' → push:
stack = [(] - Read 'A' → operand →
postfix = "A" - Read '+' → push (higher than '('):
stack = [(, +] - Read 'B' → operand →
postfix = "AB" - Read ')' → pop until '(':
- pop '+' →
postfix = "AB+" - pop '(' (discard)
stack = [] - pop '+' →
- Read '*' → stack empty → push:
stack = [*] - Read 'C' → operand →
postfix = "AB+C" - Read '-' → '-' has lower precedence than '*', so pop '*':
- pop '*' →
postfix = "AB+C*"
stack = [-] - pop '*' →
- Read 'D' → operand →
postfix = "AB+C*D" - Read '^' → higher precedence than '-', push:
stack = [-, ^] - Read 'E' → operand →
postfix = "AB+C*DE" - Read '^' → '^' is right‑associative, so we do NOT pop the previous '^'. Push new '^':
stack = [-, ^, ^] - Read 'F' → operand →
postfix = "AB+C*DEF" - End of input → pop remaining operators:
- pop '^' →
postfix = "AB+C*DEF^" - pop '^' →
postfix = "AB+C*DEF^^" - pop '-' →
postfix = "AB+C*DEF^^-"
- pop '^' →
Final postfix expression: AB+C*DEF^^-
7. Quick Review Questions & Answers (अभ्यासका लागि प्रश्नोत्तर)
- Q: Which data structure is primarily used for infix‑to‑postfix conversion?
A: Stack. - Q: In the expression
A + B * C, what is the postfix form?
A:ABC*+. - Q: How does associativity affect the handling of two '^' operators?
A: Since '^' is right‑associative, the second '^' is pushed onto the stack without popping the first. - Q: Convert
(X - Y) / (Z + W)to postfix.
A:XY- ZW+ /(without spaces:XY-ZW+/). - Q: True or False – Parentheses are never needed in postfix notation.
A: True.
Practice these steps regularly; they form a core part of the logical reasoning section in Loksewa PSC and other Nepalese competitive exams.