LEETCODE，leetcode-Basic Calculator-224

2023-11-07 阅读 29 评论 0

摘要：輸入一個字符串，包含數字或者+,-,(,)，求這個表達式的結果 1.沒有括號時順序執行 2.有括號時先計算括號內的表達式這里用一個棧來保存遇到括號(之前的表達式的結果，也就是說沒遇到括號之前，按順序正常執行設結果為x，遇到括號之后要先

輸入一個字符串，包含數字或者+,-,(,)，求這個表達式的結果

1.沒有括號時順序執行

2.有括號時先計算括號內的表達式

這里用一個棧來保存遇到括號(之前的表達式的結果，也就是說沒遇到括號之前，按順序正常執行設結果為x，遇到括號之后要先計算括號內的表達式，設結果為y，然后再把y拿出來和x順序執行。因此計算括號內的表達式時要先保存之前計算的x的值，為什么要用棧呢，因為括號可以嵌套，如a-(b-(c+d))，遇到第一個括號時，要保存a，然后進入括號，又遇到了括號要保存b，然后進入第二個括號得到c+d之后返回和b進行計算，再返回和a進行計算，這就是棧的后進先出。當然還要把符號也壓棧

LEETCODE，這里對+和-直接用一個標志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 };