tags: Leetcode medium stack python c++

227. Basic Calculator II

[題目連結:] https://leetcode.com/problems/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

解題想法:

• 給一string，求其運算後的值

  • 運算符號只會有"+ - * /"

• 想法:

  • 用一stack存所有正數, 最後加總即可
  • 對於遍歷所有符號:
    • 因為遇到乘除是要先丟完數字才能處理 所以尾巴要再多一個運算符號
  ​​​​for item in s+'+':
  

  • 因為+,-需要放在數字的前面進行判斷
    • pre_op: 為紀錄目前使用的運算子是哪個符號
    • 初始為'+'
    • cur :紀錄目前的數字
      • 避免出現 '42 + 10' ，卻判斷'42'為6的錯誤

• trace:

s = "3+2*2"
* 初始:
    pre='+'
    cur=0
    num=[]
    
for item in s+'+':

* loop1: item='3'
    cur=0+3=3
    
* loop2: item='+':
    因為pre=='+':
        num.append(cur)
    pre=item='+'
    cur=0
    
->num=[3]

* loop3: item=2
    cur=0+2=2

* loop4: item='*'
    因為pre=='+':
        num.append(cur)
    pre=item='*'
    cur=0

->num=[3,2]

* loop5: item=2
    cur=0+2=2

* loop6: item='+' //我們自己新加入的尾巴 就是為了處理乘除還沒計算到的情況
    因為pre=='*':
        num.append(num.pop()*cur)
    pre=item='+'
    cur=0
    
->num=[3,4]

所以最終sum(num)=7 
    

Python:

• 除法會遇到溢位問題，run python3沒問題

class Solution:
    def calculate(self, s: str) -> int:
        map={'+','-','*','/'}
        num=[]
        pre_op='+'
        cur=0
        for item in s+'+': #因為遇到*/是要先丟完數字才能處理 所以尾巴要再多一個運算符號
            if item==' ':
                continue
            elif item not in map:
                cur = cur*10 + int(item) #避免出現 '42 + 10'  然後記錄42為6的錯誤
            else:
                if pre_op=='+': 
                    num.append(cur)
                elif pre_op=='-':
                    num.append(-cur)
                elif pre_op=='*':
                    num.append(num.pop()*cur)
                else:
                    num.append(int(num.pop()/cur))
                cur=0
                pre_op=item
        return sum(num)

result = Solution()
ans = result.calculate(s = " 3+5 / 2 ")
print(ans)

C++:

class Solution {
public:
    int calculate(string s) {
        set<char> map={'+', '-', '*', '/'};
        long int res=0, curSum=0;
        char pre_op='+';
        string newS=s; //new string
        newS.push_back('+'); //add + to the end
        stack<int> num;
        for (char item: newS){
            if (item==' ')
                continue;
            if (map.find(item)==map.end()) //number
                curSum = curSum*10+ item-'0';
            else{
                if (pre_op=='+')
                    num.push(curSum);
                if (pre_op=='-')
                    num.push(-curSum);
                if (pre_op=='*'){
                    int top=num.top(); num.pop();
                    top*=curSum;
                    num.push(top);
                }
                if (pre_op=='/'){
                    int top=num.top(); num.pop();
                    top/=curSum;
                    num.push(top);
                }
                curSum=0;
                pre_op=item;
            }
        }
        //cal the final ans
        while (!num.empty()){
            res+=num.top();
            num.pop();
        }
        return res;
    }
};