首页 > 代码库 > leetcode-Basic Calculator-224

leetcode-Basic Calculator-224

2024-08-11 22:05:38   223人阅读

输入一个字符串，包含数字或者+,-,(,)，求这个表达式的结果

1.没有括号时顺序执行

2.有括号时先计算括号内的表达式

这里用一个栈来保存遇到括号(之前的表达式的结果，也就是说没遇到括号之前，按顺序正常执行设结果为x，遇到括号之后要先计算括号内的表达式，设结果为y，然后再把y拿出来和x顺序执行。因此计算括号内的表达式时要先保存之前计算的x的值，为什么要用栈呢，因为括号可以嵌套，如a-(b-(c+d))，遇到第一个括号时，要保存a，然后进入括号，又遇到了括号要保存b，然后进入第二个括号得到c+d之后返回和b进行计算，再返回和a进行计算，这就是栈的后进先出。当然还要把符号也压栈

这里对+和-直接用一个标志flag=1和flag=-1来表示，这样计算a-b时可以直接a+b*flag

 1 class Solution { 2 public: 3     int calculate(string s) { 4         int len=s.size(); 5         if(len==0) return 0; 6         stack<int> st; 7         int ans=0; 8         int i=0; 9         int flag=1;10         while(i<len){11             if(s[i]==‘ ‘){12                 i++;13                 continue;14             }15             if(isdigit(s[i])){16                 int num=0;17                 while(i<len&&isdigit(s[i])){18                     num=num*10+s[i]-‘0‘;19                     i++;20                 }21                 ans+=num*flag;22                 continue;23             }24             if(s[i]==‘+‘) flag=1;25             else if(s[i]==‘-‘) flag=-1;26             else if(s[i]==‘(‘){27                 st.push(ans);28                 ans=0;29                 st.push(flag);30                 flag=1;31             }32             else{33                 int a=st.top();34                 st.pop();35                 int b=st.top();36                 st.pop();37                 ans=b+a*ans;38             }39             i++;40         }41         return ans;42     }43 };

 

leetcode-Basic Calculator-224


联系
我们