1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126
|
#include <iostream> //cin, cout
#include <sstream> //stringstream, str()
#include <stack> //for stack container
#include <string> //string
#include <cctype> //isdigit()
#include <cstdlib> //exit()
using namespace std;
int prcd(char); //returns an int; the higher the int, the higher the precedence
int eval(int, int, char); //evaluates expression
int main()
{
stack<char> op; //stack for operators
string infix;
stringstream output;
cout << "Enter an arithmetic expression in infix notation.\n";
getline(cin,infix);
//CONVERTING FROM INFIX TO POSTFIX//
for(int i = 0; i < infix.size(); i++)
{
if(infix[i] == '*' || infix[i] == '/' || infix[i] == '+' || infix[i] == '-') //char from infix is *, /, +, or -
{
while(!op.empty() && prcd(op.top() >= prcd(infix[i]))) //while top of operator stack is not empty & prec is equal or greater
{
output << op.top();
op.pop();
}
op.push(infix[i]);
}
else if(infix[i] == '(') //char from infix is (
{
op.push(infix[i]);
}
else if(infix[i] == ')') //char from infix is )
{
while(!op.empty() && op.top() != '(')
{
output << op.top();
op.pop();
}
op.pop();
}
else if(isdigit(infix[i])) //char is an number
{
output << infix[i];
}
} //end of for loop
while(!op.empty())
{
output << op.top();
op.pop();
}
cout << "Postfix expression: " << output.str() << endl; //output the postfix string
string postfix = output.str();
stack<int> result;
int op1, op2;
//EVALUATING POSTFIX EXPRESSION//
for(int i = 0; i < postfix.size(); i++) //evaluate postfix expression
{
if(isdigit(postfix[i]))
{
int value = postfix[i] - '0';
result.push(value);
}
else
{
op2 = result.top();
result.pop();
op1 = result.top();
result.pop();
int value = eval(op1, op2, postfix[i]);
result.push(value);
}
} //end of for loop
cout << "The final result is " << result.top() << "." << endl;
return 0;
}
int prcd(char e) //returns an int; the higher the int, the higher the precedence
{
if(e == '*' || e == '/')
{
return 2;
}
else if(e =='+' || e == '-')
{
return 1;
}
else return 0;
}
int eval(int op1, int op2, char op) //evaluates expression
{
switch(op)
{
case '*': return op1 * op2;
break;
case '/':
if(op2 == 0)
{
cout << "Cannot divide by 0.\n";
exit(0);
}
else
{
return op1 / op2;
}
break;
case '+': return op1 + op2;
break;
case '-': return op1 - op2;
break;
default: return 0;
}
}
| |