#include <iostream>
#include <string>
#include <stack>
using namespace std;
static inline int GetPrecendence(const char &c){
switch(c){
case '+':
case '-':
return 10;
case '*':
case '/':
return 20;
default:
return 0;
}
}
static inline bool IsNum(const char &c){
return c>='0'&&c<='9';
}
static inline bool IsOp(const char &c){
bool ret=false;
if(c=='+'||c=='-'||c=='*'||c=='/'){
ret=true;
}
return ret;
}
static inline bool IsTerminator(const char &c){
bool ret=false;
if(IsOp(c)||'('==c||')'==c){
ret=true;
}
return ret;
}
static inline int Cal(const int &a,const int&b,const char& op){
std::cout<<a<<" "<<b<<" "<<op<<std::endl;
switch(op){
case '+':
return a+b;
case '-':
return a-b;
case '*':
return a*b;
case '/':
return a/b;
default:
return 0;
}
}
class Solution {
public:
int solve(string s) {
// write code here
int n=s.size();
int i=0;
int val=0;
bool num_flag=false;
while(i<n){
if(IsNum(s[i])){
val=val*10+s[i]-'0';
num_flag=true;
}
if(i==n-1||IsTerminator(s[i])){
if(num_flag){
std::cout<<val<<std::endl;
nums.push(val);
}
val=0;
num_flag=false;
}
if('('==s[i]){
ops.push(s[i]);
}else if(')'==s[i]){
while('('!=ops.top()){
int r=0;
int right=nums.top();
nums.pop();
char op=ops.top();
ops.pop();
if(IsOp(op)){
int left=nums.top();
nums.pop();
r=Cal(left,right,op);
}else{
r=right;
}
nums.push(r);
}
ops.pop();
}else if(IsOp(s[i])){
if(ops.empty()||'('==s[i]){
ops.push(s[i]);
}else if(IsOp(ops.top())&&GetPrecendence(ops.top())>=GetPrecendence(s[i])){
int right=nums.top();
nums.pop();
int left=nums.top();
nums.pop();
char op=ops.top();
ops.pop();
int r=Cal(left,right,op);
nums.push(r);
ops.push(s[i]);
}else{
ops.push(s[i]);
}
}
i++;
}
while(!ops.empty()){
int right=nums.top();
nums.pop();
int left=nums.top();
nums.pop();
char op=ops.top();
ops.pop();
int r=Cal(left,right,op);
nums.push(r);
}
int r=0;
r=nums.top();
nums.pop();
return r;
}
private:
std::stack<char> ops;
std::stack<int> nums;
};
int main(){
std::string expression="1 2 +2 + (2+2+1*2)*3";
Solution so;
int r=so.solve(expression);
std::cout<<r<<std::endl;
return 0;
}
[1] BM49 表达式求值-中等
网友评论