C++刷leetcode（面试题 16.26. 计算器）【逆波兰】

糖逗

题目描述：

给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。

表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格  。 整数除法仅保留整数部分。

示例 1:

输入: "3+2*2"
输出: 7
示例 2:

输入: " 3/2 "
输出: 1
示例 3:

输入: " 3+5 / 2 "
输出: 5
说明：

你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

    //先将中缀表达式变为后缀表达式
    queue<string> trans(string input){
        queue<string> res;
        map<char, int> store ={{'+',1},{'-',1},{'*',2},{'/',2}};
        stack<char> temp;
        for(int i = 0; i < input.size(); i++){
            if(input[i] >= '0' && input[i] <= '9'){
                string total;
                while(input[i] >= '0' && input[i] <= '9'){
                    total += input[i];
                    i++;
                }
                i--;
                res.push(total);
            }
            else if(input[i] == ' ')continue;
            else{

                if(temp.empty()) temp.push(input[i]);
                else if(store[input[i]] > store[temp.top()]){
                    temp.push(input[i]);
                }
                else if(store[input[i]] <= store[temp.top()]){//注意这里有等号！！！！
                    while(!temp.empty() &&store[input[i]] <= store[temp.top()]){  
                        string s(1, temp.top());      
                        res.push(s);
                        temp.pop();
                    }
                    temp.push(input[i]);
                }
            }
        }
        if(!temp.empty()){
            while(!temp.empty()){
                string a(1,temp.top());
                res.push(a);
                temp.pop();
            }
        }
        queue<string> temp4 = res;
        // while(!temp4.empty()){
        //     cout << temp4.front() << " ";
        //     temp4.pop();
        // }
        // cout << endl;
        return res;
    }
    int comput(queue<string> input){
        stack<int> temp;
        while(!input.empty()){
            string cha = input.front();
            // cout << cha << endl;
            if(temp.empty()){
                temp.push(stoi(cha));
            } 
            else if(cha != "+" && cha != "-" && cha != "*" && cha != "/"){
                temp.push(stoi(cha));
            }
            else{
                int temp1 = temp.top();
                temp.pop();
                int temp2 = temp.top();
                temp.pop();
                int temp3;
                if(cha == "*")  temp3 = temp1 * temp2;
                else if(cha == "-") temp3 = temp2 - temp1;
                else if(cha == "+") temp3 = temp1 + temp2;
                else if(cha == "/") temp3 = temp2 / temp1;
                // cout << temp3 << endl;
                temp.push(temp3);
                
            }
            input.pop();
        }
        return temp.top();
    }
    int calculate(string s) {
        int res = 0;
        queue<string> temp = trans(s);
        res = comput(temp);
        return res;

    }

注意事项：
1.逆波兰参考《大话数据结构》栈和队列章节内容。

糖逗

224. 基本计算器
题目描述：

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格  。

示例 1:

输入: "1 + 1"
输出: 2
示例 2:

输入: " 2-1 + 2 "
输出: 3
示例 3:

输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23
说明：

你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/basic-calculator
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    queue<string> trans(string input){
        queue<string> res;
        stack<char> temp;
        map<char, int> store = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
        for(int i = 0; i < input.size(); i++){
            if(input[i] == ' ')continue;
            else if(input[i] == '(') temp.push(input[i]);
            else if(input[i] == ')'){
                while(!temp.empty()&&temp.top()!= '('){
                    string a (1, temp.top());
                    res.push(a);
                    temp.pop();
                }
                temp.pop();
            }
            else if(input[i] >= '0' && input[i] <= '9'){
                string b;
                while(i < input.size() &&input[i] >= '0' && input[i] <= '9'){
                    b+=input[i];
                    i++;
                }
                i--;
                res.push(b);
            }
            else{
                if(temp.empty()) temp.push(input[i]);
                else if(store[input[i]] > store[temp.top()]) temp.push(input[i]);
                else{
                    while(!temp.empty() && store[input[i]] <= store[temp.top()]){
                        string c(1, temp.top());
                        res.push(c);
                        temp.pop();
                    }
                    temp.push(input[i]);
                }

            }
        }
        while(!temp.empty()){
            string d (1, temp.top());
            temp.pop();
            res.push(d);
        }
        // queue<string> temp4 = res;
        // while(!temp4.empty()){
        //     cout << temp4.front() << " ";
        //     temp4.pop();
        // }
        // cout << endl;
        return res;
    }

    int comput(queue<string> input){
        stack<int> temp;
        while(!input.empty()){
            string cha = input.front();
            if(temp.empty()){
                temp.push(stoi(cha));
            }
            else if(cha != "+" && cha != "-" && cha != "*" && cha != "/"){
                temp.push(stoi(cha));
            }
            else{
                int temp1 = temp.top();
                temp.pop();
                int temp2 = temp.top();
                temp.pop();
                int temp3;
                if(cha == "*")  temp3 = temp1 * temp2;
                else if(cha == "-") temp3 = temp2 - temp1;
                else if(cha == "+") temp3 = temp1 + temp2;
                else if(cha == "/") temp3 = temp2 / temp1;
                temp.push(temp3);
               
            }
            input.pop();
        }
        return temp.top();
    }

    int calculate(string s) {
        int res = 0;
        queue<string> input = trans(s);
        res = comput(input);
        return res;

    }
};

_2_

糖逗 发表于 2020-4-30 15:51
224. 基本计算器
题目描述：

C++ 有 eval() 吗？

糖逗

_2_ 发表于 2020-5-7 11:00
C++ 有 eval() 吗？

貌似是没有