yoruru的努力日記

227. Basic Calculator II

Given a string s which represents an expression, evaluate this expression and return its value. 

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = "3+2*2"
Output: 7

Example 2:

Input: s = " 3/2 "
Output: 1

Example 3:

Input: s = " 3+5 / 2 "
Output: 5

Constraints:

• 1 <= s.length <= 3 * 105
• s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
• s represents a valid expression.
• All the integers in the expression are non-negative integers in the range [0, 231 - 1].
• The answer is guaranteed to fit in a 32-bit integer.

SOL：

首先，最直觀的就是 先乘除後加減，所以遇到加減時，把數字存入stack中；遇到乘除時，把stack[top]取出來做運算完之後再放回stack[top]。

參考：花花酱 LeetCode 227. Basic Calculator II

解法聽起來不難，但實作時會有些細節需要注意。

1. 雖然題目的例子都是個位數，但因為 All the integers in the expression are non-negative integers in the range [0, 231 - 1]. 的題目限制，我們必須以十位數、百位數來進行處理。
所以即使讀到 s[i] 是數字，也不能立刻就寫入stack，必須讀到下一個運算符號或者是字串s結束時，才能確認 num 的大小，並放入stack中。

2. 當字串s讀到 '+', '-', '*', '/' 時，我們才能進行stack的處理。此外，要注意的是，因為字串s是中序表示法(Infix order)，所以我們讀到運算符號時無法立即處理，只能先存在 char op 中，等讀到下一個運算符號或者是字串s結束時才能最運算處理，並把資料放入stack。

中序表示法(Infix order)參考說明：前、中及後序 Preorder, Inorder and Postorder

結論：這一題我覺得是偏難的題目，除了 Basic Calculator II 之外，總共有 Basic Calculator I, II, III, IV，其中 III 鎖起來、I, IV是 hard 先不刷，我決定先只刷這一題，當然還會有更複雜的變形，例如加入大中小括號。

#define MAX_SIZE 300000

int calculate(char * s){
    int stack[MAX_SIZE];
    int top = -1;
    int num = 0;
    char op = '+'; //上一個運算符號
    for (int i = 0; s[i]!='\0'; i++){
        if(isdigit(s[i])){
            num = num*10 + (s[i]-'0');
        }
        if( !isdigit(s[i]) && !isspace(s[i]) || s[i+1]=='\0'){
            // 遇到非數字(+,-,*,/)或字串結束時，進行運算
            if(op=='+'){
                stack[++top] = num;
            }
            else if(op=='-'){
                stack[++top] = -num;
            }
            else if(op=='*'){
                stack[top] *= num;
            }
            else if(op=='/'){
                stack[top] /= num;
            }
            op = s[i];
            num=0;
        }

    }
    int answer = 0;
    while(top>-1){
        answer += stack[top--];
    }
    return answer;
}