leetcode 224 Basic Calculator

1. 问题描述

　　计算字符串表达式的值，表达式中只含有(,),+,-,空格和非负整数。例如：
　　“1 + 1” = 2
　　” 2-1 + 2 ” = 3
　　“(1+(4+5+2)-3)+(6+8)” = 23
　　原文链接：https://leetcode.com/problems/basic-calculator/

2. 方法与思路

2.1 利用后缀表达式计算

　　一种思路是按照常规的方法，由中缀表达式转到后缀表达式在进行计算。转换过程如下：
　　依次遍历字符串，做一下操作。

1. 若是操作数，入到输出栈。
2. 若是闭括号，把操作栈中的运算符依次出栈，推入输出栈，一直遇到对应开括号为止，把开括号出栈。
3. 开括号，进运算符栈。
4. 是运算符，如果运算符栈优先级高，堆栈运算符出栈，出栈操作一直要进行到栈顶运算符优先级低为止，然后把新的运算符入栈。这里加减同样的优先级，括号要高一些。
5. 操作符结束后，把运算符栈中所有剩余运算符依次出栈，放入输出栈。
6. 计算输出堆表达式的值。

class Solution {
public:
    int GetNum(string poststr,int *i)
    {
        int tmp =0;
        while(poststr[(*i)] >= ‘0‘ && poststr[(*i)] <= ‘9‘)
        {
            tmp = tmp*10 + ( poststr[(*i)] - ‘0‘);
            (*i) ++;
        }
        return tmp;
    }

    int postcal(string poststr)
    {
        stack<int> s;
        int i,a,b,tmp =0;
        for(i=0; i < poststr.length(); i++)
        {
            switch(poststr[i])
            {
                case ‘ ‘:
                    continue;
                case ‘+‘:
                    b = s.top(); s.pop();
                    a = s.top(); s.pop();
                    s.push(a+b);
                    break;
                case ‘-‘:
                    b = s.top(); s.pop();
                    a = s.top(); s.pop();
                    s.push(a-b);
                    break;
                default:
                    s.push(GetNum(poststr,&i));
            }

        }

        return s.top();
    }
    int calculate(string s) {
        int re =0,tmp = 0;
        stack<char> num;
        string poststr="";
        for(int i=0; i < s.length(); i++)
        {
            switch(s[i])
            {
                case ‘(‘:
                    num.push(s[i]); 
                    break;
                case ‘ ‘:
                    continue;
                case ‘)‘:

                    poststr += " ";
                    while(num.top() != ‘(‘)
                    {
                        poststr += num.top();
                        num.pop();

                    }
                    num.pop();
                    break;
                case ‘+‘:
                case ‘-‘:
                    poststr += " ";

                    while(!num.empty() && num.top() != ‘(‘)
                    {

                        poststr +=num.top();
                        num.pop();
                    }
                    num.push(s[i]);
                    break;
                default:
                    poststr += s[i];

            }

            }

        poststr += " ";
        while(!num.empty())
        {
            poststr += num.top();
            num.pop();
        }

        //cout<<poststr<<endl;

        return postcal(poststr);

     }
};

但是这种方法却超时了，头晕。还得好好地再看看，有没有可优化的地方！！！

2.2 表达式化简

　　由于表达式中只含有括号和加减法运算，我们可以通过加减法的规律对表达式进行化简，然后求值。
　　

class Solution {
public:
    int calculate(string s) {
        stack<int> num;
        num.push(1);

        char op = ‘+‘;        
        long re = 0;

        for (int i=0; i<s.length(); i++) {

            switch(s[i]) {
                case ‘ ‘:
                    break;
                case ‘+‘:
                case ‘-‘:
                    op = s[i];
                    break;
                case ‘(‘:
                    num.push(num.top() * (op == ‘-‘ ? -1 : 1));
                    op = ‘+‘;
                    break;
                case ‘)‘:
                    num.pop();
                    break;
                default:
                    int tmp = 0;
                    while (  s[i] >= ‘0‘ && s[i] <= ‘9‘) {
                        tmp = tmp * 10 + s[i] - ‘0‘;
                        i++;
                    }
                    i--;
                    re += (op == ‘-‘?-1:1)*num.top()*tmp;
            }
        }
        return re;
    }
};