輸入一個字符串,包含數字或者+,-,(,),求這個表達式的結果
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 };
?