leetcode 224. Basic Calculator 字符串表达式计算 + 仅仅涉及到加法减法括号运算

痛定思痛。 2022-06-08 11:59 137阅读 0赞

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 .

You may assume that the given expression is always valid.

Some examples:  
“1 + 1” = 2  
” 2-1 + 2 ” = 3  
“(1+(4+5+2)-3)+(6+8)” = 23  
Note: Do not use the eval built-in library function.

这道题就是最经典的字符串表达式的计算问题，可以先做中序转后序，然后去计算。

代码如下：

import java.util.Stack;
    
    
    
    /*
     * 我的做法是中序转后序
     * 然后在计算
     * */
    public class Solution 
    {
        public int calculate(String s) 
        {
            if(s==null || s.length() == 0) 
                return 0;
            Stack<Integer> stack = new Stack<Integer>();
            int res = 0 , sign = 1;
            for(int i=0; i<s.length(); i++) 
            {
                char c = s.charAt(i);
                if(Character.isDigit(c)) 
                {
                    int cur = c-'0';
                    while(i+1<s.length() && Character.isDigit(s.charAt(i+1))) 
                        cur = 10*cur + s.charAt(++i) - '0';
    
                    res += sign * cur;
                } else if(c=='-')
                    sign = -1;
                else if(c=='+')
                    sign = 1;
                else if( c=='(') 
                {
                    stack.push(res);
                    res = 0;
                    stack.push(sign);
                    sign = 1;
                } else if(c==')') 
                {
                    res = stack.pop() * res + stack.pop();
                    sign = 1;
                }
            }
            return res;
        }
    }

下面是C++的做法，由于本题没有涉及到乘除法，至少涉及到加减和括号运算，所以这里就直接计算了，并没有转化为后序然后再去计算，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    class Solution
    {
    public:
        int calculate(string s) 
        {
            if (s.length() <= 0)
                return 0;
            stack<int> skt;
            int res = 0, sign = 1;
            for (int i=0;i<s.length();i++)
            {
                char c = s[i];
                if (c >= '0' && c <= '9')
                {
                    int cur = c - '0';
                    while (i + 1 < s.length() && s[i + 1] >= '0' && s[i + 1] <= '9')
                        cur = cur * 10 + (int)(s[++i] - '0');
                    res += sign*cur;
                }
                else if (c == '-')
                    sign = -1;
                else if (c == '+')
                    sign = 1;
                else if (c == '(')
                {
                    skt.push(res);
                    res = 0;
                    skt.push(sign);
                    sign = 1;
                }
                else if (c == ')')
                {
                    int a = skt.top();
                    skt.pop();
                    int b = skt.top();
                    skt.pop();
                    res = a*res + b;
                    sign = 1;
                }
            }
            return res;
        }
    };