Question

Write in C++

Implement a program that can input an expression in postfix notation (see Exercise C-5.8) and output its value. As you can see, you will need to read Exercise C-5.8 to complete this programming task.

Exercise C-5.8

Postfix notation is an unambiguous way of writing an arithmetic expression without parentheses. It is defined so that if “(exp₁) o (exp₂)” is a normal fully parenthesized expression whose operation is “o”, then the postfix version of this is “pexp₁pexp₂o”, where pexp₁ is the postfix version of exp₁ and pexp₂ is the postfix version of exp₂. The postfix version of a single number or variable is just that number or variable. So, for example, the postfix version of “((5 + 2) * (8 − 3))/4” is “5 2 + 8 3 −* 4 /”. Describe a nonrecursive way of evaluating an expression in postfix notation.

Answer 1

C++ Code :

#include<iostream>
#include<stack>               // for using stack
using namespace std;
int precedence(char ch)            // for getting precedence of operators
{
   if(ch=='+' || ch=='-')           // higher precedence for higher operators
   return 1;
   if(ch=='/' || ch=='*')           // highest precedence for highest operators
   return 2;  
   return 0;           // lowest precedence for non-operators ( means for operands )
}
string Solve(string exp)           // this function will return the required postfix notation of the input arithmetic expression
{
   string postfix="";           // for storing required postfix notation ( our result )
   stack<char> s;               // stack will be used here
   for(int i=0;i<exp.length();i++)               // for each character of the input arithmetic expression
   {
       if(exp[i]=='(')           // we'll simply push the opening parenthesis into the stack
       {
           s.push(exp[i]);
           continue;
       }
       // if we found a closing parenthesis, we'll pop all the elements and append it to our result ( postfix expression ) until
       // we get any opening parenthesis. And then at last , we'll pop out the opening paranthesis too.
       if(exp[i]==')')          
       {
           while(!s.empty() && s.top() != '(')
           {
   postfix += s.top();
   s.pop();
           }
   if(!s.empty())       // At last , we are poping out the opening paranthesis too
   s.pop();
   continue;
       }
      
       // if we found any non-operator ( operand ), we'll simply append that to our result ( postfix expression )
       if(precedence(exp[i])==0)  
           postfix += exp[i];
       else
       {
    if(!s.empty())
           {
               // we'll pop out all the operators from the stack and append it to our result ( postfix expression ) until we get
               // a lower precedence operator than the current operator
   while( s.top() != '(' && (!s.empty()) && ( precedence(s.top()) >= precedence(exp[i]) ) )
               {
   postfix += s.top();
   s.pop();
   }
   s.push(exp[i]);           // at last , we'll simply push the current operator into stack
   }
   else           // if stack is empty and we encounter and operator , then we'll simply push that operator into stack
           s.push(exp[i]);
       }
   }
   // Now after iterating the complete input arithmetic expression , we'll have some operators left into the stack , so what we need
   // to do is to pop out all the remaining operators from the stack and we'll simply append them all to our required result
   while(!s.empty())
   {
       postfix += s.top();
       s.pop();
   }
   return postfix;               // returing our required result ( postfix expression )
}
int main()
{
   string exp;               // it will store the arithmetic expression input by the user
   cout<<"Enter an arithmetic expression : ";
   cin>>exp;           //   taking input of arithmetic expression from the user
   string result = Solve(exp);               // calling Solve() method which would return our required result ( postfix expression )
   cout<<" Postfix expression = "<<result;       // printing required result ( postfix expression )
}

Output 1:

Output 2: