227.Basic Calculator II

题目描述

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.

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5

Note:

• You may assume that the given expression is always valid.

• Do not use the eval built-in library function.

难度系数

Medium

解法一：先计算乘除法，同时将结果保存在双端队列中，而后再计算加减法

class Solution {
public:
    //总体思想，先计算乘除法，而后再计算加减法
    int calculate(string s) {
        deque<long long>sta_int;
        deque<char> sta_char;
        int i=0;
        long long num=0;
        while(i<s.size()){
            //将连续的数字转化为int，压入栈中，同时
            if(isdigit(s[i])){
                while (isdigit(s[i])){
                    num=num*10+s[i]-'0';
                    i++;
                }
                sta_int.push_back(num);
                num=0;
            }
            //去除字符串中的空格
            while (s[i]==' ')
                i++;
            //如果加减号则将符号压入符号栈
            if(s[i]=='+'||s[i]=='-'){
                sta_char.push_back(s[i]);
                i++;
            }
            //如果是乘除法，则直接计算结果，将结果压入数字栈中
            if(s[i]=='/'||s[i]=='*'){
                int temp=0;
                char cal=s[i];
                i++;
                //除去符号左右的空格
                while (s[i]==' ')
                    i++;
                //获取符号的后一个数字
                while (isdigit(s[i])){
                    temp=temp*10+s[i]-'0';
                    i++;
                }
                //获取符号前一个数字
                num=sta_int.back();
                sta_int.pop_back();
                //运算
                num=calc(cal,num,temp);
                sta_int.push_back(num);//结果压栈
                num=0;
            }
        }
        //正向计算加减法，如果负向计算，1-1+1，这个通不过
        int a=sta_int.front();
        sta_int.pop_front();
        if(sta_char.empty())//表示只有乘法和除法
            return a;
        else{
            //计算加减法
            while (!sta_char.empty()){
                int b=sta_int.front();
                sta_int.pop_front();
                char cal=sta_char.front();
                sta_char.pop_front();
                a=calc(cal,a,b);
            }
        }
        return a;
    }
    //四则运算
    int calc(char cal,int a,int b){
        if(cal=='+')
            return a+b;
        else if(cal=='-')
            return a-b;
        else if(cal=='*')
            return a*b;
        else
            return a/b;
    }
};

解法二：利用istringstream将数字和字符隔开

class Solution {
public:
    int calculate(string s) {
        //最后的+号是把加减的结果和乘除的结果加起来
        istringstream in(s+'+');
        long long res = 0, val;
        char op;
​
        in >> val;
        while (in >> op) {
            if (op == '+' || op == '-') {
                res += val;//计算符号的前一个值
                in >> val;
                val *= (op == '+') ? 1 : -1;//统一符号的后一个值
            } else {
                int currVal;
                in >> currVal;
                if (op == '*') {//计算当前符号左右两侧的值
                    val *= currVal;
                } else {
                    val /= currVal;
                }
            }
        }
        return res;
    }
};

解法三：将数字和运算符分别保存在两个队列中，而后再计算最终的值

class Solution {
public:
    int ptr = 0;
    int calculate(string s) {
        int num = 0;
        queue<int> num_que;//保存运算的数字
        queue<char> char_que;//保存运算符
        while (ptr < s.size()) {
            char ch = s[ptr++];
            if (ch == ' ') continue;
            if (ch >= '0' && ch <= '9') num = num*10 + (ch - '0');
            else {//运算符号
               num_que.push(num);
               char_que.push(ch);
               num=0;
            }
        }
        num_que.push(num);//将最后一个数字push到队列中
        num=num_que.front();num_que.pop();
        char_que.push('+');
        int sum=0;
        while (!char_que.empty()){
            char ch=char_que.front();char_que.pop();
            if(ch=='+'||ch=='-'){
                sum+=num;
                num=num_que.front();num_que.pop();
                num *= (ch == '+') ? 1 : -1;
            }else{
                int curVal=num_que.front();num_que.pop();
                if(ch=='*')num*=curVal;
                if(ch=='/')num/=curVal;
            }
        }
        return sum;
    }
};