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; }
No comments:
Post a Comment