题意

给定一个表达式，计算表达式的值

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

方法

递归同时计算

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

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

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

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

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

以样例数据为例，400+5

初始化为空

首先我们读入400

那么数值栈中压入

然后读入加号

读入5

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

输出数值栈的第一个

代码

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
int getExp(char *s,int n,int &idx);

int getNumber(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;
  if(o == '*')v.back()*=v1;
  if(o == '/')v.back()/=v1;
  // printf("=%d\n",v[v.size()-1]);
}

int getExp(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);
      }
    }else if(o == '*' || o == '/'){ // 优先级高
      while(op.size() && (op[op.size()-1] == '*' || op[op.size()-1] == '/')){
        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();
}


int main(){
  char s[110];
  scanf("%s",s);
  int i = 0;
  printf("%d\n",getExp(s,strlen(s),i));
  return 0;
}

复杂度分析

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

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

三步：token，ast，计算

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

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

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

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

代码

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)

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; // 符号
};

Token getNumberToken(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(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(Node{NUMBER,-ts[i++].value,0,{}});
        neg = false; // 消耗了负号
      }else{
        ns.push_back(Node{NUMBER,ts[i++].value,0,{}});
      }
    }else if(ts[i].op == '('){ // 递归找括号 表达式
      if(neg){
        ns.push_back(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);
    }else if(ts[i].op == '*' || ts[i].op == '/'){ // 乘除，注意优先级
      while(op.size() && (op.back() == '*' || op.back() == '/')){
        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]);
    if(node.op == '*')return calcAst(node.ns[0])*calcAst(node.ns[1]);
    if(node.op == '/')return calcAst(node.ns[0])/calcAst(node.ns[1]);
  };
  assert(false);
  return 0;
}


int main(){
  char s[110];
  scanf("%s",s);
  int n = strlen(s);
  // string 2 tokens
  vector<Token> ts; // tokens
  int i = 0;
  while(i < n){
    if(isdigit(s[i])){
      ts.push_back(getNumberToken(s,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
  printf("%d\n",calcAst(node));
  return 0;
}

void printAst(const Node & node,int dep = 0){ // 方便调试 查看Ast
  if(node.nt == NUMBER){
    rep(i,0,dep){
      printf("  ");
    }
    printf("%d\n",node.value);
  }else if(node.nt == EXP){
    printAst(node.ns[0],dep+1);
    rep(i,0,dep){
      printf("  ");
    }
    printf("%c\n",node.op);
    printAst(node.ns[1],dep+1);
  }else if(node.nt == NEG){
    rep(i,0,dep){
      printf("  ");
    }
    printf("-\n");
    printAst(node.ns[0],dep+1);
  }
}

复杂度分析

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

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