Convert Infix to Postfix using Stack in Python
Convert Infix to Postfix using Stack
In the realm of computer science and programming, efficiency is paramount. Converting infix expressions to postfix is a fundamental operation that can significantly impact the efficiency of your code.
In this page, we will discuss about the intricacies of infix to postfix expression conversion, providing you with a deep understanding of the process, its applications, and how to implement it effectively.
Introduction to Infix and Postfix Expressions
Infix expressions are the familiar mathematical notations that we use in everyday life. For instance, “3 + 5” or “((2 * 6) – 1).” These expressions follow operator precedence rules and can contain parentheses to indicate the order of operations.
Postfix expressions, also known as Reverse Polish Notation (RPN), are a different way of representing mathematical expressions. In postfix notation, operators come after their operands, making it easier for computers to evaluate without the need for operator precedence rules or parentheses.
Why Convert Infix to Postfix?
- Converting infix expressions to postfix has several advantages.
- It simplifies expression evaluation, eliminates the need for parentheses to indicate precedence, and allows for straightforward implementation in programming languages.
- Postfix expressions are also easily processed by computers, making them ideal for calculators and parsers.
Infix Expression Syntax:
Infix expressions are the familiar mathematical notations used in everyday mathematics. They follow the operator precedence rules, and parentheses are often used to indicate the order of operations.
operand1 operator operand2
Where:
- ‘operand1’ and ‘operand2′ are numeric values or variables.
- operator is a mathematical operator such as ‘+’ (addition), ‘-‘ (subtraction), ‘*’ (multiplication), ‘/’ (division), etc.
- Parentheses ‘(‘ and ‘)’ are used to group operations and explicitly define the order of evaluation.
(5 + 3) * 2
Postfix Expression Syntax:
Postfix expressions, also known as Reverse Polish Notation (RPN), have a different syntax. In postfix notation, operators come after their operands, and there is no need for operator precedence rules or parentheses.
operand1 operand2 operator
Where:
- ‘operand1’ and ‘operand2′ are numeric values or variables.
- operator is a mathematical operator such as ‘+’ (addition), ‘-‘ (subtraction), ‘*’ (multiplication), ‘/’ (division), etc.
Infix Expression | Postfix Expression |
---|---|
A + B | A B + |
A + B * C | A B C * + |
(A + B) * C | A B + C * |
A * (B + C) | A B C + * |
A + (B * C) – D | A B C * + D – |
A * B + C / D | A B * C D / + |
(A + B) * (C – D) | A B + C D – * |
A + B + C | A B + C + |
A * B * C | A B * C * |
Implementation of Infix to Postfix
Using Stack
# Define the Stack class class Stack: def __init__(self): self.items = [] def push(self, item): self.items.append(item) def pop(self): if not self.isEmpty(): return self.items.pop() else: return None def peek(self): if not self.isEmpty(): return self.items[-1] else: return None def isEmpty(self): return len(self.items) == 0 # This function returns the relative precedence of the operators we have # e.g divide (/) has higher precedence than multiply (*) def precedence(char): if char == '^': return 3 elif char == '/' or char == '*': return 2 elif char == '+' or char == '-': return 1 else: return 0 # Function check whether the given character is Operand or not def isOperand(char): return (ord(char) >= ord('a') and ord(char) <= ord('z')) or (ord(char) >= ord('A') and ord(char) <= ord('Z')) or (ord(char) >= ord('0') and ord(char) <= ord('9')) # Function for converting an infix expression to postfix expression def infixToPostfix(s, st): # s is the infix expression and st is the stack postFix = [] for i in range(len(s)): if isOperand(s[i]): postFix.append(s[i]) elif s[i] == '(': st.push(s[i]) elif s[i] == ')': while st.peek() != '(': postFix.append(st.peek()) st.pop() st.pop() # Pop the '(' from the stack else: while (not st.isEmpty()) and (precedence(s[i]) <= precedence(st.peek())): postFix.append(st.pop()) st.push(s[i]) while not st.isEmpty(): postFix.append(st.peek()) st.pop() return ' '.join(postFix) # Example usage: infix_expression = "a + b * (c - d) / e" stack = Stack() postfix_expression = infixToPostfix(infix_expression, stack) print(postfix_expression)
Output
a b c d - e / * +
Using Shunting Yard algorithm
def infix_to_postfix(expression): precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3} output = [] operator_stack = [] for token in expression: if token.isalnum(): output.append(token) elif token == '(': operator_stack.append(token) elif token == ')': while operator_stack and operator_stack[-1] != '(': output.append(operator_stack.pop()) operator_stack.pop() else: while operator_stack and precedence.get(token, 0) <= precedence.get(operator_stack[-1], 0): output.append(operator_stack.pop()) operator_stack.append(token) while operator_stack: output.append(operator_stack.pop()) return ' '.join(output)
Output
"3 4 2 1 - * 5 2 ^ / +"
Applications of Infix to Postfix Conversion
Infix to postfix conversion finds applications in various fields, including:
- Calculator software
- Compiler design
- Expression parsing in
- programming languages
- Mathematical software
- Spreadsheet calculations
Conclusion
Mastering the conversion of infix expressions to postfix is a valuable skill for any programmer. It not only simplifies mathematical expression evaluation but also improves the efficiency of your code. With a deep understanding of the stacks and its implementation, you are well-equipped to optimize your programming endeavors.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment