2021-10-16每日刷题打卡

力扣——栈

227. 基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

示例 1：

输入：s = “3+2*2”
输出：7
示例 2：

提示：

1 <= s.length <= 3 * 105
s 由整数和算符 (’+’, ‘-’, ‘*’, ‘/’) 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数

准备两个栈，一个存数字的int栈nums，一个存运算符的char栈op。用哈希表为运算符准备好优先级，+和-的优先级为1，*和/的优先级为2，遍历字符串，当s[i]为空格时直接跳过，为数字时就连续读取字符直到不是数字为之，把读取到的字符串数字转换为int数存入nums里；当s[i]为运算符时判断，如果op不为空，且当前op的栈顶元素比s[i]的优先级高，就进行运算，从nums栈顶先后取出两个数num1和num2，从op栈顶取出运算符，判断运算符，+：num1+num2、-：num2-num1、 *：num1 *num2、/:num2/num1。把结果存入nums里，计算结束后把s[i]的运算符插入op里。等遍历完了字符串后，用while遍历op，当op为空时退出，按照上面的运算方法依次运算。最后返回nums的顶端元素。

class Solution {
public:
    stack<int>nums;
    stack<char>op;

    void operating()
    {
        int num1 = nums.top();
        nums.pop();
        int num2 = nums.top();
        nums.pop();
        char c = op.top();
        op.pop();
        switch (c)
        {
        case '+':nums.push(num1 + num2);
            break;
        case '-':nums.push(num2 - num1);
            break;
        case '*':nums.push(num1 * num2);
            break;
        case '/':nums.push(num2 / num1);
            break;
        }
    }

    int calculate(string s) {
        int num1, num2;
        int num=0;
        unordered_map<char, int>mymap;
        mymap['+'] = mymap['-'] = 1;
        mymap['*'] = mymap['/'] = 2;
        for (int i = 0; i < s.size(); i++)
        {
            if(s[i]==' ')
            {
                continue;
            }
            else if (s[i] >= 48 && s[i] <= 57)
            {
                while (s[i] >= 48 && s[i] <= 57)
                {
                    num = num * 10 + (s[i] - 48);
                    i++;
                }
                i--;
                nums.push(num);
                num = 0;
            }
            else
            {
                while (op.size() != 0 && mymap[op.top()] >= mymap[s[i]])
                {
                    operating();
                }
                op.push(s[i]);
            }
        }
        while (op.size() != 0)
        {
            operating();
        }
        return nums.top();
    }
};