参考资料
练习题 icon lost
交流讨论
笔记
img lost

今天的题目其实就是字符串处理,比较常见。当然我得承认,这类题目做的比较少,但是在数据结构中常见,而且会告诉我们可以用栈做。而这道题目也反映出我本人眼高手低的问题,想了很长时间依然错误。接下来我将在讲述解法的同时说明我本人的问题。

Leetcode-224题目说明

实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
输入:s = "1 + 1"
输出:2
提示:
	1 <= s.length <= 3 * 10 ^ 5
	s由数字、'+'、'-'、'('、')'、和 ' ' 组成
	s表示一个有效的表达式

在很多书中都提到了用栈去解决此类问题,因此我当时的想法是使用两个栈,一个存储数字,一个存储符号,由于只有加减,因此每当遇到")“或者字符串结尾,就不断对加减进行计算。但是有个重要的问题,这相当于从后往前进行计算,特别是遇到减号的时候,就会出现错误。
在看到题解后,才明白,这里的栈其实存储的是正负号,也就是我们是该进行加法运算还是应该进行减法运算。需要注意的是”( )“里的优先级最高,并且当”( )"前的符号是减号时,括号里的所有运算符均发生改变,因此可以在栈中存储括号间的运算符,每遇到 “(” 时,就判断之前的一个运算符;每遇到 “)” ,就废弃正在使用的运算符。这其实有种递归的思想。

源码如下所示:

class Solution {
public:
    int len;

    int calculate(string s) {
        stack<int> st;
        st.push(1);
        int i = 0, len = s.size(), sum = 0, flag = 1;
        while(i < len){
            if(s[i] == ' ')
                i++;
            else if(s[i] == '+'){
                flag = st.top();
                i++;
            }else if(s[i] == '-'){
                flag = -st.top();
                i++;
            }else if(s[i] == '('){
                st.push(flag);
                i++;
            }else if(s[i] == ')'){
                st.pop();
                i++;
            }else{
                int cnt = 0;
                while(i < len && s[i] >= '0' && s[i] <= '9'){
                    cnt = (s[i] - '0') + cnt * 10;
                    i++;
                }
                sum += flag * cnt;
            }
        }
        return sum;
    }
};

由于当天有事,知道今天才去做每日一题,在此记录一下

Leetcode-227题目说明

给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
输入:s = "3+2*2"
输出:7

这一题,说实话,相比于上一题其实很简单。如果你真正搞懂了上一题,这一题的解法类似,都是使用栈,同时对运算符号做标记。只不过不同的是,这一次栈中存储的是数据,而不是运算符号。
四则运算我们可以将其看作 n 个数之和,只不过包括了乘除运算后的结果,以及负数相加。如果我们只在栈中存储加法或减法涉及的数据(减法可以转换成加法),而在遍历中进行了乘法或者除法,那么我们就解决了乘除的优先级问题。
我们使用一个 int 表示前一个运算符,由于栈中存储着待运算的数据,我们直接运算即可。例如:

1 + 2 * 3 + 4
那么在运算中,我们首先读取第一个数字 1 并存入栈中。
接着读取加号, 记录运算符。
接着读取字符 2 ,由于之前的是加号,可以在最后运算,直接存入栈中。
接着读取字符 3 ,由于我们发现之前的是乘法,需要进行演算。那么从栈顶取出 2 ,与 3 进行乘法运算并将结果 6 写入栈中。
接着读取加号, 记录运算符。
接着读取字符 4 ,由于是加号,所以直接存入栈中。
最后将栈中所有数据累加即可得到结果。

这就是大致过程,较容易理解,其代码如下所示:

class Solution {
public:
    int i = 0, len, cnt1 = 0, cnt2 = 0;
    int calculate(string s) {
        len = s.size();
        stack<int> st;
        while(i < len){
            if(s[i] == ' ')
                i++;
            else if(s[i] == ',')
                i++;
            else if(s[i] == '+'){
                cnt1 = 1;
                i++;
            }else if(s[i] == '-'){
                cnt1 = 2;
                i++;
            }else if(s[i] == '*'){
                cnt1 = 3;
                i++;
            }else if(s[i] == '/'){
                cnt1 = 4;
                i++;
            }else{
                int sum = 0;
                while(s[i] >= '0' && s[i] <= '9'){
                    sum *= 10;
                    sum += s[i] - '0';
                    i++;
                }
                if(cnt1 == 0 || cnt1 == 1){
                    st.push(sum);
                }else if(cnt1 == 2){
                    st.push(-sum);
                }else if(cnt1 == 3){
                    int t = st.top();
                    st.pop();
                    st.push(t * sum);
                }else {
                    int t = st.top();
                    st.pop();
                    st.push(t / sum);
                }
            }
        }
        int sum = 0;
        while(!st.empty()){
            sum += st.top();
            st.pop();
        }
        return sum;
    }
};
资料来源 Leetcode-224 基本计算器 && Leetcode-227 基本计算器 II
博客作者 qq_40537232
前往答题
我的笔记