一、题目描述：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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题思路

方法一。使用递归，每次遇到括号就递归计算括号里的数字再进行计算

方法二、先把中缀表达式转成后缀表达式，使用后缀表达式计算

1、中缀表达式转后缀表达式

1.遇到操作数，直接输出； 
2.栈为空时，遇到运算符，入栈； 
3.遇到左括号，将其入栈； 
4.遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出； 
5.遇到其他运算符’+”-”*”/’时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈； 
6.最终将栈中的元素依次出栈，输出。 
经过上面的步骤，得到的输出既是转换得到的后缀表达式。 
举例：a+b*c+(d*e+f)g ———> abc+de*f+g*+
2、后缀表达式计算

1、遇到操作数入栈

2、遇到计算符号从栈里取出2个数字计算后入栈

3、直到遍历完后缀表达式，栈里只剩下一个数字，就是计算结果

三、代码

class Solution {
public:
    int calculate(string s) {
        
        vector<string> houzhui = gend(s);
       print(houzhui);
        vector<string> stack;
        
        for(int i = 0; i<houzhui.size();i++)
        {
            if(houzhui[i] == "+" || houzhui[i] == "-")
            {
                string tmp1 = *stack.rbegin();
                stack.pop_back();
                string tmp2 = *stack.rbegin();
                stack.pop_back();
                if(houzhui[i] == "+")
                {
                    int sum = atoi(tmp2.c_str()) + atoi(tmp1.c_str());
                    stack.push_back(to_string(sum));
                }
                if(houzhui[i] == "-")
                {
                    int sum = atoi(tmp2.c_str()) - atoi(tmp1.c_str());
                    stack.push_back(to_string(sum));
                }
            }
            else
            {
                stack.push_back(houzhui[i]);
            }
            //cout<<"i="<<i<<endl;
            //cout<<"houzhi="<<houzhui[i]<<endl;
            //print(stack);
        }
        
        return atoi(stack.begin()->c_str());
    }
    
    vector<string> gend(string& s)
    {
        vector<string> save;
        vector<string> stack;
        string num;
        for(int i = 0; i < s.size(); i++)
        {
            //cout<<"numg="<<num<<endl;
            //cout<<"si="<<s[i]<<endl;
            if(s[i] == ' ')
                continue;
            if(s[i] >= '0' && s[i] <= '9')
            {
                num.push_back(s[i]);
                //save.push_back(string(1,s[i]));
            }
            else if(num.size() != 0)
            {
                save.push_back(num);
                num.clear();
            }

            //cout<<"s[i]="<<s[i]<<endl;
            //cout<<"num="<<num<<endl;
            if(s[i] == '(')
            {
                stack.push_back(string(1,s[i]));
                
            }
            if(s[i] == ')')
            {
                while(*stack.rbegin() != "(")
                {
  
                    save.push_back(*stack.rbegin());
                    stack.pop_back();
                }
                if(*stack.rbegin() == "(")
                {
                    stack.pop_back();
                }
            }
            if(s[i] == '+' || s[i] == '-')
            {
                while(stack.size() > 0 && (*stack.rbegin() == "+" || *stack.rbegin() == "-"))
                {
                   
                    save.push_back(*stack.rbegin());
                    stack.pop_back();
                }
                stack.push_back(string(1,s[i]));
            }

        }
        //cout<<"numg="<<num<<endl;
            if(num.size()!= 0)
            {
                save.push_back(num);
            }        
        while(stack.size() > 0)
        {
            save.push_back(*stack.rbegin());
            stack.pop_back();
        }
        
        return save;
    }
    void print(vector<string> &  str)
    {
        for(int i = 0; i< str.size(); i ++)
        {
            cout<<str[i]<<",";
        }
        cout<<endl;
    }
};