Friday, September 7, 2012

Evaluate a parenthesized expression!!


The problem can be solved by using two stacks. One for the numbers and another one for the operators. When we get a left parenthesis we ignore it. When we get an operand we push it to the number stack and when we get a operator, we push it to the operator stack. When we encounter a right parenthesis, we pop two elements from number stack, pop a operator from operator stack, perform operation on the numbers and push back the result to the number stack.
#include<iostream>
#include<stack>
using namespace std;
int main()
{
    stack<int> val;
    stack<char> op;
    string expression;
    cin>>expression;
    for(int i=0;i<expression.length();i++)
    {
        if((expression[i] - '0' >=0) && (expression[i] - '0' <=9))
            val.push(expression[i] - '0');
        else if (expression[i] == '(')
            continue;
        else if (expression[i] == '-' || expression[i] == '+' || expression[i] == '*' || expression[i] == '/')
            op.push(expression[i]);
        else if(expression[i] == ')')
        {
            if (op.empty() || val.empty())
            {
                cout<<"InCorrect number of paranthesis "<<endl;
                return -1;
            }
            else
            {
                int num1 = val.top();
                val.pop();
                if(val.empty())
                {
                    cout<<"InCorrect number of paranthesis "<<endl;
                    return -1;
                }
                int num2 = val.top();
                val.pop();
                char oper = op.top();
                op.pop();
                switch(oper)
                {
                    case '+' : val.push(num1 + num2);
                    break;
                    case '-' : val.push(num1 - num2);
                    break;
                    case '*' : val.push(num1*num2);
                    break;
                    case '/' : val.push(num1/num2);
                    break;
                }
            }
        }
        else
            continue;
    }
    cout<<val.top()<<endl;
    return 0;
}