C++ QUESTION! I need help with this question!! Please make sure you USE the EVAL
ID: 3910954 • Letter: C
Question
C++ QUESTION!
I need help with this question!! Please make sure you USE the EVALUATION ALGORITHM provided at the end of the page!!
PLEASE ADD NOTES TO THE SOLUTION SO I CAN UNDERSTAND THE CODE!
QUESTION:
Postfix evaluation
In this assignment, you are to input an infix expression, convert it to
postfix and then EVALUATE it. You should use a generic stack(i.e. a templated stack).
You are to use Dijkstra's algorithm as shown below in the conversion from infix to postfix.
Dijkstra's Algorithm:
Read in 1 line into a string
Print the string
while there are characters left to process in the string
-----
| get a token (skip over blanks)
| if the token is a digit then output(token)
| else
| -----
| | if the token is '(' then push(token)
| | else
| | -----
| | | if the token is ')' then
| | | -----
| | | | while the top item is not '('
| | | | pop(temp) and output(temp);
| | | | pop(temp)
| | | -----
| | | else
| | | -----
| | | | if the stack is empty then push(token)
| | | | else
| | | | -----
| | | | | while the stack is not empty
| | | | | and the priority (token) <= priority (top item on the stack)
| | | | | pop(temp) and output(temp)
| | | | | push(token)
| | | | -----
| | | -----
| | ----
| -----
-----
while the stack is not empty do pop(temp) and output(temp)
Precedence of the Operators:
operators : ^ * / + - (
precedence: 3 2 2 1 1 0
where ^ means exponentiation
Note: Ignore blank lines.
Input for the assignment:
a. 2 + 3 * 5
b. 2 + 3 * 5 ^ 6
c. 2 + 3 - 5 + 6 - 4 + 2 - 1
d. 2 + 3 * (5 - 6) - 4
e. 2 * 3 ^ 5 * 6 - 4
f. (2 + 3) * 6 ^ 2
g. ( ( ( ( 2 + 3 - 4 ) / 2 + 8 ) * 3 * ( 4 + 5 ) / 2 / 3 + 9 ) )
Sample output
1: 2 + 3 * 5
235*+
17
2: 2 + 3 * 5 ^ 6
2356^*+
46877
3: 2 + 3 - 5 + 6 - 4 + 2 - 1
23+5-6+4-2+1-
3
4: 2 + 3 * (5 - 6) - 4
2356-*+4-
-5
5: 2 * 3 ^ 5 * 6 - 4
235^*6*4-
2912
6: (2 + 3) * 6 ^ 2
23+62^*
180
7: ( ( ( ( 2 + 3 - 4 ) / 2 + 8 ) * 3 * ( 4 + 5 ) / 2 / 3 + 9 ) )
23+4-2/8+3*45+*2/3/9+
45
The Evaluation algorithm is as follows:
st = postfix_string
for (i=0; i < length(st); i++)
{
token = st[i]
switch (token)
{
digit :
push token
break
operator :
pop opn2
pop opn1
result = evaluate(opn1, token, opn2)
push result
break
}
}
int evaluate (int opn1, char token, int opn2)
{
switch (token)
{
case '+' : result = opn1 + opn2;
case '-' : result = opn1 - opn2;
case '*' : result = opn1 * opn2;
case '/' : result = opn1 / opn2;
case '^' : result = opn1 ** opn2; (Fortran exponentiation)
}
return result;
}
Explanation / Answer
#include <iostream>
#include <string>
#include <stack>
#include <cmath>
using namespace std;
int precedence(char exp)
{
// return precedence of operator
switch (exp)
{
case '+' : return 1;
case '-' : return 1;
case '*' : return 2;
case '/' : return 2;
case '^' : return 3;
}
return 0;
}
string infix_postfix(string str) //infix to postfix
{
string p = ""; //output string i.e. postfix string that is to be returned
int n = str.length();
stack<char> s;
for(int i=0; i<n; i++)
{
char c = str[i]; //token
if('0'<=c && c<='9') //if the token is a digit then output(token) i.e. add to output string
{
p += c;
}
else if(c=='(') //if the token is '(' then push(token)
{
s.push(c);
}
else if(c==')') //if the token is ')' then
{
while(s.top()!='(') //while the top item is not '(' pop(temp) and output(temp) i.e. add to output string
{
p+=s.top();
s.pop();
}
s.pop(); // pop the '(' from stack
}
else if(c=='+'||c=='-'||c=='*'||c=='/'||c=='^') // if the token is operator
{
if(s.empty()) //if the stack is empty then push(token)
{
s.push(c);
}
else
{
//while the stack is not empty and the priority (token) <= priority (top item on the stack)
//pop(temp) and output(temp)
while(!s.empty() && precedence(c)<=precedence(s.top()))
{
p+=s.top();
s.pop();
}
s.push(c); //push(token)
}
}
}
//while the stack is not empty
//pop(temp) and output(temp) i.e. add to output string
while(!s.empty())
{
p+=s.top();
s.pop();
}
return p;
}
int evaluate (int opn1, char token, int opn2)
{
//evaluate operand 1 and operand 2 based on input token(operator) and return the result
switch (token)
{
case '+' : return opn1 + opn2;
case '-' : return opn1 - opn2;
case '*' : return opn1 * opn2;
case '/' : return opn1 / opn2;
case '^' : return pow(opn1, opn2);
}
}
int postfix_evaluation(string str)
{
int n = str.length();
stack <int> s;
for (int i=0; i < n; i++)
{
char c = str[i]; // token
if('0'<=c && c<='9') //if token is a digit push(operand)
{
int d = c - '0'; // char to int conversion
s.push(d);
}
//if token is a operator pop(operand2) and then pop(operand1)
//then evaluate according to the operator
// operand 1 operator operand 2
else if (c=='+'||c=='-'||c=='*'||c=='/'||c=='^')
{
int op2 = s.top();
s.pop();
int op1 = s.top();
s.pop();
s.push(evaluate(op1, c, op2));
}
}
return s.top();
}
int main()
{
string in1 = "2 + 3 * 5";
cout << in1<< " ";
cout << infix_postfix(in1)<< " ";
cout << postfix_evaluation(infix_postfix(in1))<< " ";
string in2 = "2 + 3 * 5 ^ 6";
cout << in2<< " ";
cout << infix_postfix(in2) << " ";
cout << postfix_evaluation(infix_postfix(in2))<< " ";
string in3 = "2 + 3 - 5 + 6 - 4 + 2 - 1";
cout << in3<< " ";
cout << infix_postfix(in3) << " ";
cout << postfix_evaluation(infix_postfix(in3))<< " ";
string in4 = "2 + 3 * (5 - 6) - 4";
cout << in4<< " ";
cout << infix_postfix(in4) << " ";
cout << postfix_evaluation(infix_postfix(in4))<< " ";
string in5 = "2 * 3 ^ 5 * 6 - 4";
cout << in5<< " ";
cout << infix_postfix(in5) << " ";
cout << postfix_evaluation(infix_postfix(in5))<< " ";
string in6 = "(2 + 3) * 6 ^ 2";
cout << in6<< " ";
cout << infix_postfix(in6) << " ";
cout << postfix_evaluation(infix_postfix(in6))<< " ";
string in7 = "( ( ( ( 2 + 3 - 4 ) / 2 + 8 ) * 3 * ( 4 + 5 ) / 2 / 3 + 9 ) )";
cout << in7<< " ";
cout << infix_postfix(in7) << " ";
cout << postfix_evaluation(infix_postfix(in7))<< " ";
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.