Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

关于stack的经典题,需要一个符号栈和一个数字栈。

如果遇到的是数字,就将其解析,注意此时有可能出现多个连续数字构成多位数的情况,通过不断读入然后每次将原先数字乘10加新数字,最终就可以将string数字解析为int,然后push入数字栈。

如果遇到符号,有四种情况:

  1. 空格:直接跳过
  2. ‘(‘: 直接push入符号栈
  3. ‘+’ or ‘-‘ : 如果符号栈顶不是运算符,则push此符号入栈,否则取出数字栈顶两个数字进行符号栈顶符号的运算,然后再push回符号栈,最后讲栈顶运算符换成当前运算符
  4. ’)’: pop符号栈,如果遇到运算符就进行3中类似的运算,直到遇到‘(‘

C++ solution (20ms)



class Solution {
public:
    int numStack[10000];
    char expStack[10000];
    int numPtr = -1, expPtr = -1;
    
    int strToInt(string s)
    {
        int num = 0;
        for(int i = s.length() - 1; i >= 0; --i)
            num += (s[i] - '0') * pow(10, s.length() - 1 - i);
        return num;
    }
    
    int calculate(string s) {
        int ptr = 0;
        while(ptr < s.length())
        {
            if(s[ptr] == ' ') ++ptr;
            else if(s[ptr] >= '0' && s[ptr] <= '9')
            {
                int num = 0;
                do
                {
                    num = num * 10 + (s[ptr++] - '0');
                }while(ptr < s.length() && (s[ptr] >= '0' && s[ptr] <= '9'));
                numStack[++numPtr] = num;
            }
            else
            {
                if(s[ptr] == '(') expStack[++expPtr] = s[ptr];
                else if(s[ptr] == '+' || s[ptr] == '-')
                {
                    if(expPtr == -1 || (expStack[expPtr] != '+' && expStack[expPtr] != '-')) expStack[++expPtr] = s[ptr];
                    else 
                    {
                        if(expStack[expPtr] == '+') numStack[numPtr - 1] = numStack[numPtr - 1] + numStack[numPtr--];
                        else numStack[numPtr - 1] = numStack[numPtr - 1] - numStack[numPtr--];
                        expStack[expPtr] = s[ptr];
                    }
                }
                else
                {
                    while(expStack[expPtr] != '(')
                    {
                        if(expStack[expPtr] == '+') numStack[numPtr - 1] = numStack[numPtr - 1] + numStack[numPtr--];
                        else numStack[numPtr - 1] = numStack[numPtr - 1] - numStack[numPtr--];
                        --expPtr;
                    }
                    --expPtr;
                }
                ++ptr;
            }
        }
        int res = numStack[0];
        for(int i = 0; i <= expPtr; ++i)
        {
            if(expStack[i] == '+') res += numStack[i + 1];
            if(expStack[i] == '-') res -= numStack[i + 1];
        }
        return res;
    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *