Convert an infix expression into a postfix expression
Given an infix expression, convert it to the postfix expression. Assume that the infix expression is a string of tokens without any whitespace.
For example,
Input: A*B+C
Output: AB*C+
Input: (A+B)*(C/D)
Output: AB+CD/*
Input: A*(B*C+D*E)+F
Output: ABC*DE*+*F+
Input: (A+B)*C+(D-E)/F+G
Output: AB+C*DE-F/+G+
Output: AB*C+
Input: (A+B)*(C/D)
Output: AB+CD/*
Input: A*(B*C+D*E)+F
Output: ABC*DE*+*F+
Input: (A+B)*C+(D-E)/F+G
Output: AB+C*DE-F/+G+
The idea is to use the stack data structure to convert an infix expression to a postfix expression. The stack is used to reverse the order of operators in postfix expression. The stack is also used to hold operators since an operator can’t be added to a postfix expression until both of its operands are processed.
The following algorithm will output a string in postfix order. We process the infix expression from left to right. For each token, four cases can arise:
- If the current token is an opening bracket,
'(', push it into the stack. - If the current token is a closing bracket,
')', pop tokens from the stack until the corresponding opening bracket ‘(‘ is removed. Append each operator at the end of the postfix expression. - If the current token is an operand, append it at the end of the postfix expression.
- If the current token is an operator, push it on the top of the stack. Before doing that, first pop from the stack till we have a lower precedence operator on top, or the stack becomes empty. Append each operator at the end of the postfix expression.
Finally, append any remaining operators in the stack at the end of the postfix expression and return the postfix expression. Following is the pictorial representation of the above logic for the infix expression A*(B*C+D*E)+F:
Following is the implementation of the above algorithm in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include <iostream> #include <stack> #include <string> #include <climits> using namespace std; // Utility function to return precedence of the given operator. // Note that higher is the precedence, lower is its value int prec(char c) { // Multiplication and division if (c == '*' || c == '/') { return 3; } // Addition and subtraction if (c == '+' || c == '-') { return 4; } // Bitwise AND if (c == '&') { return 8; } // Bitwise XOR (exclusive or) if (c == '^') { return 9; } // Bitwise OR (inclusive or) if (c == '|') { return 10; } // add more operators if needed return INT_MAX; // for opening bracket '(' } // Utility function to check if a given token is an operand bool isOperand(char c) { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); } // Function to convert an infix expression to a postfix expression. // This function expects a valid infix expression string infixToPostfix(string infix) { // create an empty stack for storing operators stack<char> s; // create a string to store the postfix expression string postfix; // process the infix expression from left to right for (char c: infix) { // Case 1. If the current token is an opening bracket '(', // push it into the stack if (c == '(') { s.push(c); } // Case 2. If the current token is a closing bracket ')' else if (c == ')') { // pop tokens from the stack until the corresponding opening bracket '(' // is removed. Append each operator at the end of the postfix expression while (s.top() != '(') { postfix.push_back(s.top()); s.pop(); } s.pop(); } // Case 3. If the current token is an operand, append it at the end of the // postfix expression else if (isOperand(c)) { postfix.push_back(c); } // Case 4. If the current token is an operator else { // remove operators from the stack with higher or equal precedence // and append them at the end of the postfix expression while (!s.empty() && prec(c) >= prec(s.top())) { postfix.push_back(s.top()); s.pop(); } // finally, push the current operator on top of the stack s.push(c); } } // append any remaining operators in the stack at the end of the postfix expression while (!s.empty()) { postfix.push_back(s.top()); s.pop(); } // return the postfix expression return postfix; } int main() { string infix = "A*(B*C+D*E)+F"; string postfix = infixToPostfix(infix); cout << postfix << endl; return 0; } |
Output:
ABC*DE*+*F+
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
import java.util.Stack; class Main { // Utility function to return precedence of the given operator. // Note that higher is the precedence, lower is its value public static int prec(char c) { // Multiplication and division if (c == '*' || c == '/') { return 3; } // Addition and subtraction if (c == '+' || c == '-') { return 4; } // Bitwise AND if (c == '&') { return 8; } // Bitwise XOR (exclusive or) if (c == '^') { return 9; } // Bitwise OR (inclusive or) if (c == '|') { return 10; } // add more operators if needed return Integer.MAX_VALUE; // for opening bracket '(' } // Utility function to check if a given token is an operand public static boolean isOperand(char c) { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); } // Function to convert an infix expression to a postfix expression. // This function expects a valid infix expression public static String infixToPostfix(String infix) { // base case if (infix == null || infix.length() == 0) { return infix; } // create an empty stack for storing operators Stack<Character> s = new Stack<>(); // create a string to store the postfix expression String postfix = ""; // process the infix expression from left to right for (char c: infix.toCharArray()) { // Case 1. If the current token is an opening bracket '(', // push it into the stack if (c == '(') { s.add(c); } // Case 2. If the current token is a closing bracket ')' else if (c == ')') { // pop tokens from the stack until the corresponding opening // bracket '(' is removed. Append each operator at the end // of the postfix expression while (s.peek() != '(') { postfix += s.pop(); } s.pop(); } // Case 3. If the current token is an operand, append it at the end // of the postfix expression else if (isOperand(c)) { postfix += c; } // Case 4. If the current token is an operator else { // remove operators from the stack with higher or equal precedence // and append them at the end of the postfix expression while (!s.isEmpty() && prec(c) >= prec(s.peek())) { postfix += s.pop(); } // finally, push the current operator on top of the stack s.add(c); } } // append any remaining operators in the stack at the end // of the postfix expression while (!s.isEmpty()) { postfix += s.pop(); } // return the postfix expression return postfix; } public static void main(String[] args) { String infix = "A*(B*C+D*E)+F"; String postfix = infixToPostfix(infix); System.out.println(postfix); } } |
Output:
ABC*DE*+*F+
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
import sys from collections import deque # Utility function to return precedence of the given operator. # Note that higher is the precedence, lower is its value def prec(c): # Multiplication and division if c == '*' or c == '/': return 3 # Addition and subtraction if c == '+' or c == '-': return 4 # Bitwise AND if c == '&': return 8 # Bitwise XOR (exclusive or) if c == '^': return 9 # Bitwise OR (inclusive or) if c == '|': return 10 # add more operators if needed return sys.maxsize # for opening bracket '(' # Utility function to check if a given token is an operand def isOperand(c): return ('a' <= c <= 'z') or ('A' <= c <= 'Z') or ('0' <= c <= '9') # Function to convert an infix expression to a postfix expression. # This function expects a valid infix expression def infixToPostfix(infix): # base case if not infix or not len(infix): return True # create an empty stack for storing operators s = deque() # create a string to store the postfix expression postfix = '' # process the infix expression from left to right for c in infix: # Case 1. If the current token is an opening bracket '(', push it into # the stack if c == '(': s.append(c) # Case 2. If the current token is a closing bracket ')' elif c == ')': # pop tokens from the stack until the corresponding opening bracket '(' # is removed. Append each operator at the end of the postfix expression while s[-1] != '(': postfix += s.pop() s.pop() # Case 3. If the current token is an operand, append it at the end of the # postfix expression elif isOperand(c): postfix += c # Case 4. If the current token is an operator else: # remove operators from the stack with higher or equal precedence # and append them at the end of the postfix expression while s and prec(c) >= prec(s[-1]): postfix += s.pop() # finally, push the current operator on top of the stack s.append(c) # append any remaining operators in the stack at the end of the postfix expression while s: postfix += s.pop() # return the postfix expression return postfix if __name__ == '__main__': infix = 'A*(B*C+D*E)+F' postfix = infixToPostfix(infix) print(postfix) |
Output:
ABC*DE*+*F+
The time complexity of the above solution is O(n), where n is the length of the infix expression. The auxiliary space required by the program is O(n) for the stack data structure.
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)