题意

给定一个包含加减括号的表达式，计算表达式的值

限制：

表达式长度不大于100000，计算过程保证在int内，只包含 数字 加减乘除 和 括号，保证表达式正确

方法

递归同时计算

考虑表达式，其实是由数值 运算符 数值 运算符 数值 运算符构成的

其中第一个数值可能是负号开始，可以通过判断起始字符进行处理

所有数值 可能是括号表达式，可以通过判断前括号进行处理

当我们处理掉括号和负数以后。

我们可以用栈来完成表达式计算。

以400+5为例

初始化为空

首先我们读入400

那么数值栈中压入

然后读入加号

读入5

字符串读取完，处理栈的末尾

输出数值栈的第一个

代码

class Solution {
public:
    int getNumber(const char * s, int n, int & idx){ // 获得数值
      if(s[idx] == '('){ // 是括号表达式
        return getExp(s,n,idx);
      }
      int v = 0;
      while(isdigit(s[idx])){ // 值
        v*=10;
        v+=s[idx]-'0';
        idx++;
      }
      return v;
    }

    void calc(vector<int> & v,vector<char> & op){ // 计算栈末尾
      int v1 = v.back();
      int o = op.back();
      v.pop_back();
      op.pop_back();
      // printf("%d %c %d",v0,o,v1);
      if(o == '-')v.back()-=v1;
      if(o == '+')v.back()+=v1;
      // printf("=%d\n",v[v.size()-1]);
    }

    int getExp(const char *s,int n,int &idx){ // 获取表达式
      int firstch = s[idx]; // 首个字符
      vector<int>vals = {};
      vector<char> op = {};
      if(firstch == '-' || firstch == '('){ // 负号 或 左括号
        idx++;
      }
      // number op number op number op number
      int v = getNumber(s,n,idx); // 获得第一个数值
      vals.push_back(firstch =='-'?-v:v); // 负数处理
      // printf("PUSH:%d\n",vals[vals.size()-1]);
      while(idx < n){
        if(firstch == '(' && s[idx] == ')'){ // 匹配的右括号
          while(op.size()){ // 清理栈上内容
            calc(vals,op);
          }
          idx++;
          return vals.front();
        }
        char o = s[idx];
        if(o == '-' || o == '+'){ // 加减优先级低
          while(op.size()){
            calc(vals,op);
          }
        }
        op.push_back(o);
        // printf("PUSH:%c\n",op[op.size()-1]);
        idx++;
        vals.push_back(getNumber(s,n,idx));
        // printf("PUSH:%d\n",vals[vals.size()-1]);
      }
      while(op.size()){ // 清理栈上内容
        calc(vals,op);
      }
      return vals.front();
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int calculate(string s) {
        int i = 0;
        return getExp(s.c_str(),s.length(),i);
    }
};

复杂度分析

时间复杂度: 我们每个字符至多读取访问两遍，每个字符操作复杂度都是常数，所以总时间复杂度为$O(n)O(n)$

空间复杂度: 最坏情况把整个内存中都储存了表达式的所有内容，所以空间复杂度为$O(n)O(n)$

三步：token，ast，计算(TLE)

上面过程中是解析和计算同步进行，对于想扩展时可能代码较难更改。

我们如果把整个分成三个步骤

1. 字符串到一定不会分为两部分的token转换
2. token序列到计算二叉树
3. 计算二叉树的值

这样去实现，那么如果有扩展需求，会更容易更改

代码

enum NODE_TYPE {NUMBER,EXP,NEG}; // 数值，双目表达式，负表达式

struct Node{
  NODE_TYPE nt;

  int value; // 数值

  char op; // 双目表达式的运算符
  vector<struct Node *> ns;
};

enum TOKEN_TYPE {OP,NUM};

struct Token{
  TOKEN_TYPE tt;
  int value; // 值
  char op; // 符号
};

class Solution {
public:
    Token getNumberToken(const char * s,int& idx,int n){ // 获取不含符号的数字
      int v = 0;
      while(idx < n && isdigit(s[idx])){
        v*=10;
        v+=s[idx] - '0';
        idx++;
      }
      return Token{NUM,v,0};
    }

    void zipNode(vector<Node*> &ns, vector<char> &ops){ // 把栈的末尾合并成一个Exp Node
      Node* n1 = ns.back();
      ns.pop_back();
      Node* n0 = ns.back();
      ns.pop_back();
      char op = ops.back();
      ops.pop_back();
      ns.push_back(new Node{EXP,0,op,{n0,n1}});
    }

    Node* genAst(const vector<Token> & ts,int & i){ // 生成Ast
      bool lbrace = false;
      bool neg = false;
      if(ts[i].tt == OP && ts[i].op == '('){ // 左括号
        lbrace = true;
        i++;
      }
      if(ts[i].tt == OP && ts[i].op == '-'){ // 负号
        neg = true;
        i++;
      }
      vector<Node*> ns = {};
      vector<char> op;

      // Node op Node op Node op Node 运算的结构
      while(i < int(ts.size())){
        if(ts[i].tt == NUM){ // 数值
          if(neg){
            ns.push_back(new Node{NUMBER,-ts[i++].value,0,{}});
            neg = false; // 消耗了负号
          }else{
            ns.push_back(new Node{NUMBER,ts[i++].value,0,{}});
          }
        }else if(ts[i].op == '('){ // 递归找括号 表达式
          if(neg){
            ns.push_back(new Node{NEG,0,0,{genAst(ts,i)}});
            neg = false; // 消耗了负号
          }else{
            ns.push_back(genAst(ts,i));
          }
        }else if(ts[i].op == ')'){ // 右括号 返回整个表达式Node
          assert(lbrace);
          while(op.size()){
            zipNode(ns,op);
          }
          i++;
          return ns[0];
        }else if(ts[i].op == '+' || ts[i].op == '-'){ // 加减运算，前面栈上的优先级更高
          while(op.size()){
            zipNode(ns,op);
          }
          op.push_back(ts[i++].op);
        }
      }
      while(op.size()){ // 处理结束
        zipNode(ns,op);
      }
      return ns[0];
    }

    int calcAst(const Node * node) { // 运算 二叉树
      if(node->nt == NEG){
        return -calcAst(node->ns[0]);
      }
      if(node->nt == NUMBER){
        return node->value;
      }
      if(node->nt == EXP){
        if(node->op == '+')return calcAst(node->ns[0])+calcAst(node->ns[1]);
        if(node->op == '-')return calcAst(node->ns[0])-calcAst(node->ns[1]);
      };
      return 0;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    int calculate(string s) {
        // string 2 tokens
        vector<Token> ts; // tokens
        int i = 0;
        int n = s.length();
        const char * si = s.c_str();
        while(i < n){
            if(isdigit(s[i])){
              ts.push_back(getNumberToken(si,i,n));
            }else{
              ts.push_back(Token{OP,0,s[i++]});
            }
        }
        // for(auto k :ts){
        //   printf("%d %d %c\n",k.tt,k.value,k.op);
        // }
        i = 0;
        // tokens to ast
        Node* node = genAst(ts, i);
        // printAst(node);
        // calculate ast
        return calcAst(node);
    }
};

复杂度分析

时间复杂度: 整个字符串每个位置的访问次数是常数次，所以总时间复杂度为$O(n)O(n)$, 但是

空间复杂度: 建立的ast和读入的储存都是字符串的常数倍，所以空间复杂度为为$O(n)O(n)$