LC150.逆波兰表达式求值

思路：

• 利用堆栈进行逆波兰式求值
• 如果遇到整数，就入栈
• 如果遇到符号，就将最上面的两个数字弹栈，进行运算之后得到新的数字，并入栈
• 最后一定只剩下一个数字，那个数字就是最终得数
• 字符串转整数的细节比较繁琐

  代码：

class Solution {
public:
    int stringToNum(string num_string) {
        if (num_string == "*" || num_string == "/" || num_string == "+" || num_string == "-") {
            return 0x3f3f3f3f;
        }
        bool negative = false;
        int res_num = 0;
        int begin_pos = 0, end_pos = num_string.size() - 1;
        // 读掉符号
        if (num_string[0] == '-') {
            negative = true;
            begin_pos = 1;
        } else if (num_string[0] == '+') {
            begin_pos = 1;
        } 
        for (int i = begin_pos; i <= end_pos; ++i) {
            res_num = (res_num * 10 + (num_string[i] - '0'));
        } 
        return res_num * (negative == false ? 1 : -1);
    }
    int evalRPN(vector<string>& tokens) {
        stack<int> post_expr;
        int len_tokens = tokens.size();
        for (int i = 0; i < len_tokens; ++i) {
            if (stringToNum(tokens[i]) >= -200 && stringToNum(tokens[i]) <= 200) {
                post_expr.push(stringToNum(tokens[i]));
            } else {
                int num2 = post_expr.top();
                post_expr.pop();
                int num1 = post_expr.top();
                post_expr.pop();
                int new_num = 0;
                if (tokens[i] == "*") {
                    new_num = num1 * num2;
                } else if (tokens[i] == "/") {
                    new_num = num1 / num2;
                } else if (tokens[i] == "+") {
                    new_num = num1 + num2;
                } else if (tokens[i] == "-") {
                    new_num = num1 - num2;
                }
                post_expr.push(new_num);
            }
        }
        return post_expr.top();
    }
};