表达式计算

  • 一般借助数据结构栈来完成，特别是带有括号的表达式
  • 常见的运算表达式
    • 中缀表达式 操作数① 运算符② 操作数③ 例如 1 + 1
    • 后缀表达式 操作数① 操作数③ 运算符② 例如 1 1 +
  • 求解没有括号的中缀表达式时，可以概括为：遇到乘除立即算，遇到加减先入栈
    • 乘除立即算：把栈顶的元素和当前的元素进行*或者/的计算
    • 加减先入栈：+号将当前数字进栈，-号将当前数的相反数进栈
  • 表达式的难点在于各个操作符的优先级

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int clumsy(int N){
    Deque<Integer> t = new LinkedList<>();
    t.push(N);
    int op = 0;
    for(int i = N - 1; i > 0; i-- ){
        if(op % 4 == 0) t.push(t.pop() * i); // * 乘
        else if(op % 4 == 1) t.push(t.pop() / i); // / 除
        else if(op % 4 == 2) t.push(i); // + 加
        else t.push(-i); // - 减
        op++;
    }
    int res = 0;
    while(!t.isEmpty()){
        res += t.pop();
    }
    return res;
}

复杂度分析

  • 时间复杂度：O(N)。从N到1进栈一次，出栈一次
  • 空间复杂度：O(N)。