Programming Problem C++: Write a program to implement the algorithm for evaluati

Question

Programming Problem C++:
Write a program to implement the algorithm for evaluating postfix expressions that involve only singledigit integers and the integer operations: +, - , *, and /. To trace the action of postfix evaluation, display each token as it is encountered, and display the action of each stack operation. Your program should output an error message if the postfix expression is not well formed. I.e. not correct.
For example given the expression 9 2 1 + / 4 * the output of your program should resemble the following:
Token = 9 Push 9

Token = 2 Push 2

Token = 1 Push 1

Token = + Pop 1 Pop 2 Push 3

Token = / Pop 3 Pop 9 Push 3

Token = 4 Push 4  

Token = * Pop 4 Pop 3 Push 12

Token = Pop 12
The algorithm for evaluating postfix expressions is given below.
ALGORITHM TO EVALUATE POSTFIX EXPRESSIONS
Each time an operand is encountered, it is pushed onto the stack. When an operator is encountered, the top two values are popped from the stack, the operator applied to them, and the result pushed back onto the stack. The following algorithm summarizes this procedure:
1. Initialize an empty stack 2. Repeat the following until the end of the expression is encountered: a) Get the next token (character, variable, arithmetic operator) in the postfix expression.
b) If token is an operand, push it onto the stack. If it is an operator, do the following:   i) Retrieve and pop the top two values from the operand stack. If the operand stack does not contain two items, an error due to a malformed postfix expression has occurred and evaluation is terminated.   ii) Apply the operator token to these two values. iii) Push the resulting value back onto the operand stack.
3. When the end of the expression is encountered, its value is on top of the stack (and in fact must be the only value in the stack).

Explanation / Answer

Code:

#include <iostream>
#include <cstdlib>
#include<string>
#include<stack>
#include<vector>
using namespace std;
vector<string> sttok(string str) //function to convert input string separate vector of tokens
{
int i=0;
vector<string> res;
string temp="";
for(i=0;i<str.size();i++)
{

if(str[i]==' ')
{
res.push_back(temp);
temp="";
}
else
{
temp.push_back(str[i]);
}
}
res.push_back(temp);
return res;

}
int strtoint(string str) //function to convert input string to integer
{
int i=0;
int sum=0;
while(i<str.size())
{
int c=str.at(i)-48;
sum=sum*10 +c;
i++;
}
return sum;
}

int evalpostfix(vector<string> tokens) { // function for evaluation of postfix expression

int returnValue = 0;

string operators = "+-*/";

stack<int> st; //use operand stack
int i=0;

for(i=0;i<tokens.size();i++){ //t is tokens[i]
cout<<"Token ="<<tokens[i]<<" ";
if(operators.find(tokens[i])==-1){ //if it is operand then push into the stack
cout<<"Push "<<tokens[i]<<endl;
st.push(strtoint(tokens[i]));
}else{ //if it is operator
int a = st.top();
st.pop(); //pop first element from stack
cout<<"Pop "<<a;
int b = st.top();
cout<<" Pop "<<b;
st.pop(); //pop second element from stack
char c = tokens[i][0];
switch(c){ //check which which operator it is
case '+':
cout<<" Push "<<a+b<<endl;
st.push(a+b);
break;
case '-':
st.push(b-a);
cout<<" Push "<<b-a<<endl;
break;
case '*':
st.push(a*b);
cout<<" Push "<<a*b<<endl;
break;
case '/':
st.push(b/a);
cout<<" Push "<<b/a<<endl;
break;
}
}
}
cout<<"Token = Pop "<<st.top(); //at the end top of stack contains the result
return st.top();
}

int main()
{
string str= "9 2 1 + / 4 *";
evalpostfix(sttok(str));

return 0;
}

Sample Input and Output:

Token =9 Push 9
Token =2 Push 2
Token =1 Push 1
Token =+ Pop 1 Pop 2 Push 3
Token =/ Pop 3 Pop 9 Push 3
Token =4 Push 4
Token =* Pop 4 Pop 3 Push 12
Pop 12

If you have any doubt then please comment below

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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