Nepal Standard Time --:-- NST
लोक सेवा आयोग (Loksewa PSC) #Loksewa PSC #Infix to Postfix #Stack Algorithm #Computer Operator #Data Structures

Algorithm to Convert Infix Expressions to Postfix Notation with Step‑by‑Step Example

Tulasi Nepali
Tulasi Nepali Developer & Educator
Nov 16, 2026 Updated Nov 16, 2026 4 min read
Algorithm to Convert Infix Expressions to Postfix Notation with Step‑by‑Step Example
Font:

Tulasi Nepali Learning Platform

tulasinepali.com.np • Official Educational & Exam Preparation Notes

Date: 2026-11-18
Subject: लोक सेवा आयोग (Loksewa PSC)

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)

  1. Initialize an empty stack opStack and an empty output string postfix.
  2. Read the infix expression token by token from left to right.
  3. If the token is an operand, append it to postfix.
  4. If the token is an ‘(’, push it onto opStack.
    • This marks a new sub‑expression.
  5. If the token is a ‘)’, pop from opStack and append each popped operator to postfix until ‘(’ is encountered. Discard both parentheses.
  6. 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.
  7. 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

AspectInfix NotationPostfix Notation
Human readabilityHigh – natural algebraic formLow – requires learning
Evaluation methodRequires precedence parsing or recursionSimple stack‑based evaluation
Parentheses neededOften required to indicate orderNever required
Computer implementationComplex (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.

  1. Initialize: stack = [], postfix = ""
  2. Read '(' → push: stack = [(]
  3. Read 'A' → operand → postfix = "A"
  4. Read '+' → push (higher than '('): stack = [(, +]
  5. Read 'B' → operand → postfix = "AB"
  6. Read ')' → pop until '(':
    • pop '+' → postfix = "AB+"
    • pop '(' (discard)
    stack = []
  7. Read '*' → stack empty → push: stack = [*]
  8. Read 'C' → operand → postfix = "AB+C"
  9. Read '-' → '-' has lower precedence than '*', so pop '*':
    • pop '*' → postfix = "AB+C*"
    Push '-': stack = [-]
  10. Read 'D' → operand → postfix = "AB+C*D"
  11. Read '^' → higher precedence than '-', push: stack = [-, ^]
  12. Read 'E' → operand → postfix = "AB+C*DE"
  13. Read '^' → '^' is right‑associative, so we do NOT pop the previous '^'. Push new '^': stack = [-, ^, ^]
  14. Read 'F' → operand → postfix = "AB+C*DEF"
  15. End of input → pop remaining operators:
    • pop '^' → postfix = "AB+C*DEF^"
    • pop '^' → postfix = "AB+C*DEF^^"
    • pop '-' → postfix = "AB+C*DEF^^-"

Final postfix expression: AB+C*DEF^^-

7. Quick Review Questions & Answers (अभ्यासका लागि प्रश्नोत्तर)

  1. Q: Which data structure is primarily used for infix‑to‑postfix conversion?
    A: Stack.
  2. Q: In the expression A + B * C, what is the postfix form?
    A: ABC*+.
  3. 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.
  4. Q: Convert (X - Y) / (Z + W) to postfix.
    A: XY- ZW+ / (without spaces: XY-ZW+/).
  5. 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.

What do you feel about this note?

0%
Love
0%
Happy
0%
Haha
0%
Sad
0%
Angry
Be the first to react!

Related Study Notes

TN
Tulasi Nepali Desk
WhatsApp Study Help

Have questions about Loksewa, notes, MCQs, or tools? Message directly on WhatsApp.

Chat on WhatsApp
Direct study help & inquiries