题目描述

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.

 

题目大意

实现一个最基本的计算器，输入一个字符串，字符串中只包含 ‘0-9’，‘+’，‘-’，‘*’，‘/’，‘ ’。

 

示例

E1

E2

E3

 

解题思路

算法要比LeetCode-224简单一些，由于没有小括号，只需要依次从左至右计算就好，可以使用一个数组来保存四个运算符的优先值，在进行计算的时候，将当前的运算符与栈顶保存的运算符比较优先级，若优先级较高则入栈，否则先将栈顶的运算符计算完毕。

 

复杂度分析

时间复杂度：O(N)

空间复杂度：O(N)

 

代码

class Solution {public:    int calculate(string s) {        int len = s.length();        // 将字符串转变为优先级数组中的索引位置，方便之后的比较        oti['+'] = 0;        oti['-'] = 1;        oti['*'] = 2;        oti['/'] = 3;        // 依次遍历字符串        for(int i = 0; i < len; ++i) {            // 遇到空格跳过            if(s[i] == ' ')                continue;            // 遇到数字入栈            else if(s[i] >= '0' && s[i] <= '9') {                int tmp = s[i] - '0', j = i + 1;                while(j < len && s[j] >= '0' && s[j] <= '9') {                    tmp *= 10;                    tmp += s[j] - '0';                    ++j;                }                i = j - 1;                num.push(tmp);            }            // 遇到操作符进行优先级判断，再进行计算和入栈操作            else {                while(!op.empty()) {                    if(!prio[oti[op.top()]][oti[s[i]]])                        break;                    cal();                }                op.push(s[i]);            }        }        while(num.size() > 1)             cal();                return num.top();    }    // 将栈顶的两个数字按照操作数栈顶的运算方法计算    void cal() {        int a, b, res;        char o = op.top();        b = num.top(); num.pop();        a = num.top(); num.pop();        op.pop();        switch(o) {            case '+' : res = a + b; break;            case '-' : res = a - b; break;            case '*' : res = a * b; break;            case '/' : res = a / b; break;        }        num.push(res);    }    private:    // 保存四个运算符的优先级大小，顺序依次为‘+’，‘-’，‘*’，‘\’    bool prio[4][4] = {        {
    true, true, false, false},        {
    true, true, false, false},        {
    true, true, true, true},        {
    true, true, true, true}    };    stack
     
       num;    stack
      
        op;    map
       
         oti;};