leetcode 227. Basic Calculator II 字符串表达式计算+减乘除没有括号的表达式计算

古城微笑少年丶 2022-06-08 12:07 160阅读 0赞

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, \*, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:  
“3+2\*2” = 7  
” 3/2 ” = 1  
” 3+5 / 2 ” = 5  
Note: Do not use the eval built-in library function.

这道题就是最经典的字符串表达式的计算问题，可以先做中序转后序，然后去计算，可以参考上一道题[leetcode 224. Basic Calculator 字符串表达式计算][leetcode 224. Basic Calculator]

代码如下：

import java.util.Stack;
    
    public class Solution 
    {
        public int calculate(String s)
        {
            int len;
            if(s==null || (len = s.length())==0) 
                return 0;
    
            Stack<Integer> stack = new Stack<Integer>();
            int num = 0;
            char sign = '+';
            for(int i=0;i<len;i++)
            {
                if(Character.isDigit(s.charAt(i)))
                    num = num*10+s.charAt(i)-'0';
    
                if((!Character.isDigit(s.charAt(i)) &&' '!=s.charAt(i)) || i==len-1)
                {
                    if(sign=='-')
                        stack.push(-num);
    
                    if(sign=='+')
                        stack.push(num);
    
                    if(sign=='*')
                        stack.push(stack.pop()*num);
    
                    if(sign=='/')
                        stack.push(stack.pop()/num);
    
                    sign = s.charAt(i);
                    num = 0;
                }
            }
    
            int re = 0;
            for(int i:stack)
                re += i;
    
            return re;
        }
    }

下面是C++的做法，就是做一个遍历，很不错的做法

**注意for循环中的两个if是并列的**

代码如下：

#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 num = 0;
            char sign = '+';
            for (int i = 0; i < s.length(); i++)
            {
                if (s[i] >= '0' && s[i] <= '9')
                    num = num * 10 + (int)(s[i] - '0');
    
                if (!(s[i] >= '0' && s[i] <= '9') && s[i] != ' ' || i == s.length() - 1)
                {
                    if (sign == '-')
                        skt.push(-num);
                    else if (sign == '+')
                        skt.push(num);
                    else if (sign == '*')
                    {
                        int tmp = skt.top()*num;
                        skt.pop();
                        skt.push(tmp);
                    }
                    else if (sign == '/')
                    {
                        int tmp = skt.top()/num;
                        skt.pop();
                        skt.push(tmp);
                    }
    
                    sign = s[i];
                    num = 0;
                }
            }
    
            int res = 0;
            while (skt.empty() == false)
            {
                res += skt.top();
                skt.pop();
            }
            return res;
        }
    };

[leetcode 224. Basic Calculator]: http://blog.csdn.net/jackzhang_123/article/details/78082759