A postfix expression is an arithmetic expression where an operator appears after

Question

A postfix expression is an arithmetic expression where an operator appears after its operands. For example, in the postfix notation, "3+4" will be represented as "3 4 +", and "( ( 4 + 5 ) - 3 ) * 2" represented as "4 5 + 3 - 2 *". The notation we normally use is called "infix notation", e.g., "3 + 4", and "( ( 4 + 5 ) - 3 ) * 2". It is called infix because the operator always appears in the middle of the two operands.

Given a postfix arithmetic expression, we can use a stack to evaluate its value, as follows. The picture below shows an example on how the postfix version of "( ( 4 + 5 ) - 3 ) * 2" is evaluated with a stack. The algorithm scans the postfix expression, from left to right

Each time we read an operand we push it into a stack.

Each operator in a postfix string refers to the previous two operands in the string. When we reach an operator, its operands will then be top two elements on the stack. We can thepop these two elements, perform the indicated operation on them, and push the result on the stack, so that it will be available for use as an operand of the next operator (the values 9 and 6 in the picture below are such examples: 9 is the result of 4+5, and 6 is the result of 9-3).

Write a function called evaluate_postfix(), with the following signature:

int evaluate_postfix(string sExp)

This function takes a postfix notation string as input parameter (sExp), and evaluates it and returns its value as an integer.

Your function must support exactly the following four operators and all of their combinations: + - * /.

In your main function, create multiple postfix expressions to thoroughly test your function, like the following:

string s1 = "10 20 + 20 -";
string s2 = "30 2 10 * -";
string s3 = "30 20 10 - -";
string s4 = "30 20 - 10 - ";
cout<

which should create the following output:

10 20 + 20 - = 10
30 2 10 * - = 10
30 20 10 - - = 20
30 20 - 10 - = 0

To evaluate a postfix expression, you need a way to break it into operands and operators. E.g., given s1 above, you need to be able to break it into five strings: "10", "20", "+", "20", and "-". To accomplish this, consider using C++'s stringstream class. As a result, make sure you add a space between all pairs of consecutive operators and operands.

To use stringstream, add header in your code. Then you can use the >> operator to extract space-separated "words", the same way as cout.

string op1, op2, operator;

stringstream ss("10 20 +");

ss >> op1; // 10

ss >> op2; // 20

ss >> operator; // +

You also need a way to convert from a string representation to an integer, and back. Use the following two functions that I wrote:

// converts string to integer

int strToInt(string op){
int i=0;
stringstream number(op);
number>>i;
return i;
}

// converts from integer to string
string intToStr(int i){
stringstream ss;
ss< return ss.str();
}

Explanation / Answer

/*
Evaluation Of postfix Expression in C++
Input Postfix expression must be in a desired format.
Operands must be integers and there should be space in between two operands.
Only '+' , '-' , '*' and '/' operators are expected.
*/
#include<iostream>
#include<stack>
#include<string>

using namespace std;

// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression);

// Function to perform an operation and return output.
int PerformOperation(char operation, int operand1, int operand2);

// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C);

// Function to verify whether a character is numeric digit.
bool IsNumericDigit(char C);

int main()
{
   string expression;
   cout<<"Enter Postfix Expression ";
   getline(cin,expression);
   int result = EvaluatePostfix(expression);
   cout<<expression<<" = "<<result<<" ";
}

// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression)
{
   // Declaring a Stack from Standard template library in C++.
   stack<int> S;

   for(int i = 0;i< expression.length();i++) {

       // Scanning each character from left.
       // If character is a delimitter, move on.
       if(expression[i] == ' ' || expression[i] == ',') continue;

       // If character is operator, pop two elements from stack, perform operation and push the result back.
       else if(IsOperator(expression[i])) {
           // Pop two operands.
           int operand2 = S.top(); S.pop();
           int operand1 = S.top(); S.pop();
           // Perform operation
           int result = PerformOperation(expression[i], operand1, operand2);
           //Push back result of operation on stack.
           S.push(result);
       }
       else if(IsNumericDigit(expression[i])){
           // Extract the numeric operand from the string
           // Keep incrementing i as long as you are getting a numeric digit.
           int operand = 0;
           while(i<expression.length() && IsNumericDigit(expression[i])) {
               // For a number with more than one digits, as we are scanning from left to right.
               // Everytime , we get a digit towards right, we can multiply current total in operand by 10
               // and add the new digit.
               operand = (operand*10) + (expression[i] - '0');
               i++;
           }
           // Finally, you will come out of while loop with i set to a non-numeric character or end of string
           // decrement i because it will be incremented in increment section of loop once again.
           // We do not want to skip the non-numeric character by incrementing i twice.
           i--;

           // Push operand on stack.
           S.push(operand);
       }
   }
   // If expression is in correct format, Stack will finally have one element. This will be the output.
   return S.top();
}

// Function to verify whether a character is numeric digit.
bool IsNumericDigit(char C)
{
   if(C >= '0' && C <= '9') return true;
   return false;
}

// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C)
{
   if(C == '+' || C == '-' || C == '*' || C == '/')
       return true;

   return false;
}

// Function to perform an operation and return output.
int PerformOperation(char operation, int operand1, int operand2)
{
   if(operation == '+') return operand1 +operand2;
   else if(operation == '-') return operand1 - operand2;
   else if(operation == '*') return operand1 * operand2;
   else if(operation == '/') return operand1 / operand2;

   else cout<<"Unexpected Error ";
   return -1;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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