Hot Topics
Data Structure
Convert Infix to Postfix
Problem:
Given an infix expression in the form of string str. Convert this infix expression to postfix expression.
Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands.
Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands.
Note: The order of precedence is: ^ greater than * equals to / greater than + equals to -.
Example 1
Input:str=”a+b*(c^d-e)^(f+g*h)-i”
Output: abcd^e-fgh*+^*+i-
Explanation:
After converting the infix expression into postfix expression, the resultant
expression will be abcd^e-fgh*+^*+i-
Example 2
Input:str=tr = “A*(B+C)/D”
Output:ABC+*D/
Explanation:
After converting the infix expression into postfix expression, the resultant
expression will be ABC+*D/
NOTE:You should know precedence table
Approach
Iterate through the given string
If we find a operand then print it
If an opening bracket ‘(‘ is found then push it into a stack
If an closing bracket ‘)’ is found then we will be popping out elements from stack and print it until we find an opening bracket ‘(‘.
If the stack is empty and we find an operator then we push it into stack.Else we compare with the top operator in stack and check for the precedence.
If the precedence is higher for that operator then we push into stack else keep popping from stack and print till we find lower precedence operator.
Once we have finished traversing through the expression, we keep popping out elements from stack and print it.
Here is the code:
#include
using namespace std;
// Function to return precedence of operators
int prec(char c)
{
if (c == '^')
return 3;
else if (c == '/' || c == '*')
return 2;
else if (c == '+' || c == '-')
return 1;
else
return -1;
}
// The main function to convert infix expression to postfix expression
void infixToPostfix(string s)
{
stack st; // For stack operations, we are using
// C++ built in stack
string result;
for (int i = 0; i <s>= 'a' && c = 'A' && c = '0' && c <= '9'))
result += c;
// If the scanned character is an
// ‘(‘, push it to the stack.
else if (c == '(')
st.push('(');
// If the scanned character is an ‘)’,
// pop and to output string from the stack
// until an ‘(‘ is encountered.
else if (c == ')')
{
while (st.top() != '(')
{
result += st.top();
st.pop();
}
st.pop();
}
// If an operator is scanned
else
{
while (!st.empty() && prec(s[i]) <= prec(st.top()))
{
result += st.top();
st.pop();
}
st.push(c);
}
}
// Pop all the remaining elements from the stack
while (!st.empty())
{
result += st.top();
st.pop();
}
cout << "Postfix expression is: " << result << endl;
}
int main()
{
// given infix string
string str = "a+b*(c^d-e)^(f+g*h)-i";
cout << "Infix expression is: " << str << endl;
// function call
infixToPostfix(str);
return 0;
}
Output
Infix expression is: a+b*(c^d-e)^(f+g*h)-i
Postfix expression is: abcd^e-fgh*+^*+i-
Automata Fixing