Postfix operators come after their arguments. Standard math notation like “4+3*7

Question

Postfix operators come after their arguments. Standard math notation like “4+3*7” is called infix, so the same expression in postfix would be “4 3 7 * +”. Note that “4 3 + 7 *” would be incorrect because the multiplication has higher precedence. Stacks are good for evaluating postfix expressions: see a number -> push onto stack; see an operator -> apply operator to two numbers popped from stack and then push result.

Write C++-like code to convert infix expressions to postfix expressions. You function should use a stack. You may assume that the input is an array (or vector) of symbols (numbers or operators ? {+, ?, ?, /, %} ) and not a string. Explain why your function is correct. Please write LEGIBLY for grading.

Explanation / Answer

Firstly, there are some assumptions and pre-requisites taken for answer to be correct:

The function to convert infix expressions to postfix expressions is as below:

bool isOperator(char ch)
{
if(ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='%')
return true;
return false;
}
int precedence(char ch)
{
if(ch=='+' || ch=='-')
return 1;
if(ch=='*' || ch=='/')
return 2;
if(ch=='%')
return 3;
}
vector<char> infixToPostfix(vector<char> V)
{
stack<char> S;
int v=V.size();
vector<char> R;
R.clear();
for(int i=0;i<v;i++)
{
if(isOperator(V[i]))
{
if(S.empty() || precedence(V[i])>precedence(S.top()))
{
S.push(V[i]);
}
else
{
while(!S.empty() && precedence(V[i])<=precedence(S.top()))
{
R.push_back(S.top());
S.pop();
}
S.push(V[i]);
}
}
else
{
R.push_back(V[i]);
}
}
while(!S.empty())
{
R.push_back(S.top());
S.pop();
}
return R;
}

Proof of correctness:

A postfix expression is evaluated from left to right i.e. whichever operator comes first is evaluated. So, to ensure correct expression output we need to ensure the operator precedences ourselves and the use of stack comes handy here.
1. All numbers comes in same order as in infix expressions. So for numbers, we simply have to add them to resultant expression.
2. The stack contains operators in decreasing order of precedence from top to bottom.
3. When we encounter a operator, there can be three different case:
Case I : Stack is empty.
In this case, we simply have to add operator to stack as it's position in postfix expression will be evaluated based on upcoming operators.
Case II : The precedence of new operator is greater than operator on top of stack.
In this case, new operator needs to be evaluated before others (currently in stack) as it's precendence is greater than all operators in stack. So, we just push new operator to stack.
Case III : The precedence of new operator is less than or equal to operator on top of stack.
In this case, the operator on top of stack stack to be evaluated before new operator. So, we add the operator on top of stack to the end of resultant expression and remove it from the stack. We do this operation until stack is empty or precedence of operator on top of stack is greater than new operator.
4. If stack is not empty, add operator removing from top of stack to the end of resultant expression until stack is empty.
5. After doing so, our postfix expression is ready and we can return this at the end of function.

So, this program is correct as this decides which operator to be executed in which order depending on precedence of the operator and hence it's evaluation will be same as input infix expression.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.