LeetCode-224. Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open 

(

 and closing parentheses 

)

, the plus 

+

 or minus sign 

-

, non-negative integers and empty spaces .

Example 1:

Input: "1 + 1"
Output: 2
           

Example 2:

Input: " 2-1 + 2 "
Output: 3
           

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23
           

Note:

• You may assume that the given expression is always valid.
• Do not use the 

  eval

   built-in library function.

題目：實作一個隻有加減法的電腦，輸入中包含小括号、正整數、空格，傳回計算的結果

思路：考察棧的題目，int棧一個存放計算數和括号，char棧存放計算符号，空格不操作。具體來說，周遊s，如若s[i]是左括号則進棧，我定義MAX代替；如果是整數且棧為空或者棧頂元素為MAX，此時數字進棧，注意掃描s時，當出現數字時，需繼續向後掃描以提取多位的整數；如果是整數而棧頂元素也是整數，則取出符号棧頂元素并進行計算，将計算結果重新入棧；如果是右括号，将數字棧連續出棧兩次，并将括号裡面的數字入棧并檢驗棧頂是否需要再次計算。最後傳回數字棧頂即可。

代碼：

#define MAX 10000000
class Solution {
public:
    int calculate(string s) {
        stack<char> sign;
        stack<int> number;
        int size = s.size();
        for(int i=0;i<size;i++){
        	if(s[i]=='(')
        		number.push(MAX); //左括号入數字棧，用MAX替代
        	else if(s[i]>='0'&&s[i]<='9'){ //出現數字，相後掃描獲得完整數
        		int s_val=0; 
        		int j;
				for(j=i;s[j]>='0'&&s[j]<='9';j++){
					s_val = s_val*10+s[j]-'0';
				}
				i=j-1; //相後多位後，更新i的值
        		if(number.empty()||number.top()==MAX)
        			number.push(s_val);  //獲得的整數入棧
        		else{                    //取出符号棧頂和數字棧頂進行計算
        			char op = sign.top();
        			sign.pop();
        			int val=0;
        			if(op=='+')
        			    val = number.top() + (s_val);	
					if(op=='-')
						val = number.top() - (s_val);
					number.pop();
					number.push(val);  //計算結果入棧
				}
			}
			else if(s[i]==')'){ //相當于去除一對括号
				int temp = number.top();
				number.pop();
				number.pop();
				if(!sign.empty()){ //通過符号棧是否為空來判斷去除括号後是否需要繼續進行計算
					char op = sign.top();
					sign.pop();
					int val=0;
					if(op=='+')
						val = number.top() + temp;
					if(op=='-')
						val = number.top() - temp;
					number.pop();
					number.push(val);
				}
				else
					number.push(temp);  //不需要計算時
			}
			else if(s[i]=='+'||s[i]=='-') //計算符号入棧
				sign.push(s[i]);
			else //空格不做處理
				;						
		}
		return number.top(); //最後隻剩數字棧頂，傳回即可
    }
};
           

AC，beats 99.6%