leetcode 计算器问题

面试题 16.26. 计算器

224. 基本计算器

227. 基本计算器 II

题目类型描述

本类型的题目就是模拟计算器的实现，运算符包括+-*/^()等，对于本类问题，使用双栈便可解决，思路便是使用两个栈，一个保存操作数，一个保存运算符，对于运算符的优先级，使用map保存优先级。

(1) 如果当前为"("，那么就把该运算符入栈，考虑到(可能直接跟着-，所以判断(如果带着-，那么就在操作数栈里面加一个0，操作数栈入栈-

(2) 如果当前为")", 那么就一直出运算符栈，一直遇到），在运算过程中逐步把运算结果入栈。

(3) 如果当前为数字字符，那么把数字字符串转为数字，然后入操作数栈

(4)如果当前为运算符+-*/^，那么就要先把运算符里面比当前运算符的优先级高的先运算掉，如果遇到(，也要停止

注意为了防止第一个字符就是-，最开始操作数栈加一个0

代码实现

class Solution {
public:
    map<char,int>op_pir={
        {'+',1},
        {'-',1},
        {'*',2},
        {'/',2},
        {'^',3}
    };
    stack<int>nums;
    stack<char>ops;
    void cal()
    {
        int a=nums.top();nums.pop();
        int b=nums.top();nums.pop();
        char op=ops.top();ops.pop();
        int res=0;
        if(op=='+')
            res=b+a;
        else if(op=='-')
            res=b-a;
        else if(op=='*')
            res=b*a;
        else if(op=='/')
            res=b/a;
        nums.push(res);


    }
    int calculate(string s) {
        int len = s.size();
        nums.push(0);
        for ( int i=0;i<len; i++)
        {
            if(s[i]==' ')
                continue;
            else if(s[i]=='(')
            {
                ops.push(s[i]);
                if(s[i+1]=='-')
                {
                    i++;
                    ops.push(s[i]);
                    nums.push(0);
                }
            }
            else if(s[i]==')')
            {
                while(!ops.empty()&&ops.top()!='(')
                {
                    cal();
                }
                ops.pop();
            }
            else if(s[i]>='0'&&s[i]<='9')
            {
                string snum="";
                while(i<len&&s[i]>='0'&&s[i]<='9')snum+=s[i++];
                i--;
                nums.push(stoi(snum));
            }
            else
            {
                while(!ops.empty()&&ops.top()!='('&&op_pir[ops.top()]>=op_pir[s[i]])cal();
                ops.push(s[i]);
            }
            
        }
        while(!ops.empty()) cal();
        return nums.top();
    }
};