题解 | #表达式求值#

#include <cstdlib>
#include <iostream>
#include <string>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        int num_r = 0;
        // 去括号
        int r_index = s.find_first_of(')');
        while(r_index != -1){
            // print
            cout<<"s: "<<s.c_str()<<endl;
            // 查找与之对应的左括号
            int l_index = 0;
            for(int i = r_index-1; i >= 0; i--){
                if(s[i]=='('){
                    l_index = i;
                    break;
                }
            }
            // print
            cout<<"( index: "<<l_index<<endl;
            cout<<") index: "<<r_index<<endl;
            // 获得两括号内部算式
            string ps;
            ps.assign(s.begin()+l_index+1, s.begin()+r_index);
            // 计算两括号内部算式结果
            num_r = calculate(ps);
            // 以局部结果更新总体算式
            updates(s, l_index, r_index, num_r);
            // 更新右侧括号位置
            r_index = s.find_first_of(')');
        }
        // 无括号
        num_r = calculate(s);
        return num_r;
    }

    int calculate(string ps){
        // 统计运算符和运算数
        vector<int> num_array;  // 记录运算数
        vector<char> op_array;  // 记录运算符
        string num_s = "";      // 字符转数字的buff
        bool if_must_num = true;// 用于生成负数
        for(char c:ps){
            if(if_must_num){
                num_s.push_back(c);
                if(c=='-') if_must_num = true;
                else if_must_num = false;
            }
            else{
                if(c=='+' || c=='-' || c=='*'){
                    op_array.push_back(c);

                    num_array.push_back(atoi(num_s.c_str()));
                    num_s.clear();
                    if_must_num = true;
                }
                else{
                    num_s.push_back(c);
                    if_must_num = false;
                }
            }
        }
        // 为num_array加入算式最后一个数
        num_array.push_back(atoi(num_s.c_str()));
        // print
        cout<<"ps :"<<ps.c_str()<<endl;
        cout<<"num_array :";
        for(int i:num_array){
            cout<<i<<", ";
        }
        cout<<endl;
        cout<<"op_array :";
        for(char i:op_array){
            cout<<i<<", ";
        }
        cout<<endl;
        // 计算乘法
        auto iter_op = op_array.begin();
        auto iter_num = num_array.begin();
        for(int i=0;i<op_array.size();i++){
            if(op_array[i]=='*'){
                // 计算运算符前后两个数的值
                int num_f = num_array[i];
                int num_e = num_array[i+1];
                int num_r = num_f * num_e;
                // 删除运算符以及运算符前后的两个数值
                op_array.erase(iter_op+i);
                num_array.erase(iter_num+i);
                num_array[i] = num_r;
                // 保证i的值
                i--;
            }
        }
        // 计算加减
        while(op_array.size()){
            // 获得运算数
            int num_f = num_array[0];
            int num_e = num_array[1];
            int num_r = 0;
            // 运算
            if(op_array[0]=='+'){
                num_r = num_f + num_e;
            }
            else{
                num_r = num_f - num_e;
            }
            // 删除运算符以及运算前后两个数值
            op_array.erase(op_array.begin());
            num_array.erase(num_array.begin());
            num_array[0] = num_r;
        }
        // 获得结果
        return num_array[0];
    }

    void updates(string &s, int l_index, int r_index, int num_r){
        auto iter_s = s.begin();
        // 删除左右括号以及括号内的内容
        for(int i=l_index;i<r_index+1;i++){
            s.erase(iter_s+l_index);
        }
        // 将括号内的结果转换为字符串插入到算式中
        string num_r_s = to_string(num_r);
        // ptint
        cout<<"num_r_s: "<<num_r_s<<endl;
        for(int i=0; i<num_r_s.size(); i++){
            s.insert(iter_s+l_index+i, num_r_s[i]);
        }
    }
};