Hello) This is my code for converting from a infix expression to a postfix one , however I just can't understand how can I evaluate the postfix expression that I get and I will be very grateful for any tips. I am not asking for a code although that would be helpful.
#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool operation(char b)
{
return b=='+' || b=='-' || b=='*' || b=='/' ;
}
bool priority(char a, char b)
{
if(a=='(')
{
return true;
}
if(a=='+' || a=='-')
{
return true;
}
if(b=='+' || b=='-')
{
return false;
}
return true;
}
int main()
{
string a;
string res;
stack<char> s;
cin>>a;
for(int i=0; i<a.size(); i++)
{
if(a[i]!='(' && a[i]!=')' && operation(a[i])==false)
{
res=res+a[i];
}
if(a[i]=='(')
{
s.push(a[i]) ;
}
if(a[i]==')')
{
while(s.top()!='(')
{
res+=s.top();
s.pop();
}
s.pop();
}
if(operation(a[i])==true)
{
if(s.empty() || (s.empty()==false && priority(s.top(), a[i])) )
{
s.push(a[i]);
}
else
{
while(s.empty()==false && priority(s.top(),a[i])==false )
{
res+=s.top();
s.pop();
}
s.push(a[i]) ;
}
}
}
while(s.empty()==false)
{
res+=s.top();
s.pop();
}
cout<<res;
return 0;
}
P.S. I don't have any comments but I suppose that the code itself is self-explanatory))
P.P.S. Thank you in advance.
If you form your posfix expression separated by space, following will be one of the easiest way to code the evaluator, just merely following the algorithm of evaluation
This assumes RPN like 5 1 2 + 4 * + 3 - (separated by space)
int evaluate_posfix ( const std::string& expression )
{
int l,r,ans;
std::stringstream postfix(expression);
std::vector<int> temp;
std::string s;
while ( postfix >> s )
{
if( operation(s[0]) )
{
//Pull out top two elements
r = temp.back();
temp.pop_back();
l = temp.back();
temp.pop_back();
// Perform the maths
switch( s[0])
{
case '+': ans = l + r ; break;
case '-': ans = l - r ; break;
case '*': ans = l * r ; break;
case '/': ans = l / r ; break; // check if r !=0
}
temp.push_back( ans ); // push the result of above operation
}
else
{
temp.push_back( std::stoi(s) );
}
}
return temp[0] ; //last element is the answer
}
Try this code (Tested on VS2019):
// CPP program to evaluate a given
// expression where tokens are
// separated by space.
#include <string>
#include <stack>
#include <iostream>
// Function to find precedence of
// operators.
int precedence(char op) {
if (op == '+' || op == '-')
return 1;
if (op == '*' || op == '/')
return 2;
return 0;
}
// Function to perform arithmetic operations.
int applyOp(int a, int b, char op) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
}
// Function that returns value of
// expression after evaluation.
int evaluate(std::string tokens) {
int i;
// stack to store integer values.
std::stack <int> values;
// stack to store operators.
std::stack <char> ops;
for (i = 0; i < tokens.length(); i++) {
// Current token is a whitespace,
// skip it.
if (tokens[i] == ' ')
continue;
// Current token is an opening
// brace, push it to 'ops'
else if (tokens[i] == '(') {
ops.push(tokens[i]);
}
// Current token is a number, push
// it to stack for numbers.
else if (isdigit(tokens[i])) {
int val = 0;
// There may be more than one
// digits in number.
while (i < tokens.length() &&
isdigit(tokens[i]))
{
val = (val * 10) + (tokens[i] - '0');
i++;
}
values.push(val);
}
// Closing brace encountered, solve
// entire brace.
else if (tokens[i] == ')')
{
while (!ops.empty() && ops.top() != '(')
{
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
// pop opening brace.
ops.pop();
}
// Current token is an operator.
else
{
// While top of 'ops' has same or greater
// precedence to current token, which
// is an operator. Apply operator on top
// of 'ops' to top two elements in values stack.
while (!ops.empty() && precedence(ops.top())
>= precedence(tokens[i])) {
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
// Push current token to 'ops'.
ops.push(tokens[i]);
}
}
// Entire expression has been parsed at this
// point, apply remaining ops to remaining
// values.
while (!ops.empty()) {
int val2 = values.top();
values.pop();
int val1 = values.top();
values.pop();
char op = ops.top();
ops.pop();
values.push(applyOp(val1, val2, op));
}
// Top of 'values' contains result, return it.
return values.top();
}
int main() {
std::cout << evaluate("10 + 2 * 6") << "\n";
std::cout << evaluate("100 * 2 + 12") << "\n";
std::cout << evaluate("100 * ( 2 + 12 )") << "\n";
std::cout << evaluate("100 * ( 2 + 12 ) / 14");
return 0;
}
// This code is contributed by Nikhil jindal.
--
Article: Expression Evaluation
