最近学了一下“递归下降分析器”，因此来练一下手。

先不考虑多余的括号，一个词法上合法的表达式应该满足以下文法：

expression  = add_expr ;
add_expr    = mul_expr
            | mul_expr ("+" | "-") add_expr ;
mul_expr    = pow_expr
            | pow_expr ("*" | "/") pow_expr ;
pow_expr    = factor
            | factor ^ pow_expr ;
factor      = "(" expression ")"
            | number ;
number      = ["+" | "-"] ('1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9')
              {('0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9')} ;

因此，对于每一行文法，可以编写一个匹配函数用于匹配。

对于本题，可以在匹配的过程中直接计算表达式的结果；在更多应用中，这可以被用于建立抽象语法树。

对于括号的处理，可以在表达式前加入足够的左括号 ( 并忽略最后右括号的失配。

Rust 实现如下，可惜 SDSY 暂时不支持 Rust。

struct Parser {
    expr: String,
    position: usize,
}

impl Parser {
    pub fn new(expr: String) -> Self {
        Parser { expr, position: 0 }
    }

    pub fn parse(&mut self) -> Result<i64, String> {
        let result = self.parse_add_expr()?;
        // while self.position < self.expr.len() {
        //     if self.expr.chars().nth(self.position).unwrap() == ' ' {
        //         self.position += 1;
        //     } else {
        //         return Err(format!(
        //             "unexpected character: {}",
        //             self.expr.chars().nth(self.position).unwrap()
        //         ));
        //     }
        // }
        Ok(result)
    }

    fn parse_add_expr(&mut self) -> Result<i64, String> {
        let mut result = self.parse_mul_expr()?;
        while self.position < self.expr.len() {
            let op = self.expr.chars().nth(self.position).unwrap();
            if op == ' ' {
                self.position += 1;
                continue;
            } else if op == '+' {
                self.position += 1;
                let rhs = self.parse_mul_expr()?;
                result += rhs;
            } else if op == '-' {
                self.position += 1;
                let rhs = self.parse_mul_expr()?;
                result -= rhs;
            } else {
                break;
            }
        }
        return Ok(result);
    }

    fn parse_mul_expr(&mut self) -> Result<i64, String> {
        let mut result = self.parse_pow_expr()?;
        while self.position < self.expr.len() {
            let op = self.expr.chars().nth(self.position).unwrap();
            if op == ' ' {
                self.position += 1;
                continue;
            } else if op == '*' {
                self.position += 1;
                let rhs = self.parse_pow_expr()?;
                result *= rhs;
            } else if op == '/' {
                self.position += 1;
                let rhs = self.parse_pow_expr()?;
                if rhs == 0 {
                    Err("division by zero".to_string())?;
                }
                result /= rhs;
            } else {
                break;
            }
        }
        return Ok(result);
    }

    fn parse_pow_expr(&mut self) -> Result<i64, String> {
        let mut result = self.parse_primary()?;
        while self.position < self.expr.len() {
            let op = self.expr.chars().nth(self.position).unwrap();
            if op == ' ' {
                self.position += 1;
                continue;
            } else if op == '^' {
                self.position += 1;
                let rhs = self.parse_pow_expr()?;
                result = result.pow(rhs as u32);
            } else {
                break;
            }
        }
        return Ok(result);
    }

    fn parse_primary(&mut self) -> Result<i64, String> {
        while self.position < self.expr.len()
            && self.expr.chars().nth(self.position).unwrap() == ' '
        {
            self.position += 1;
        }
        if self.position >= self.expr.len() {
            return Err("unexpected end of input".to_string());
        }
        let ch = self.expr.chars().nth(self.position).unwrap();
        if ch == '(' {
            self.position += 1;
            let result = self.parse_add_expr()?;
            while self.position < self.expr.len()
                && self.expr.chars().nth(self.position).unwrap() == ' '
            {
                self.position += 1;
            }
            if self.position < self.expr.len()
                && self.expr.chars().nth(self.position).unwrap() == ')'
            {
                self.position += 1;
            } else {
                // return Err("expected ')'".to_string());
            }
            return Ok(result);
        } else {
            return self.parse_number();
        }
    }

    fn parse_number(&mut self) -> Result<i64, String> {
        while self.position < self.expr.len()
            && self.expr.chars().nth(self.position).unwrap() == ' '
        {
            self.position += 1;
        }
        let mut sign = 1;
        if self.position < self.expr.len() {
            if self.expr.chars().nth(self.position).unwrap() == '-' {
                sign = -1;
                self.position += 1;
            } else if self.expr.chars().nth(self.position).unwrap() == '+' {
                self.position += 1;
            }
        }
        while self.position < self.expr.len()
            && self.expr.chars().nth(self.position).unwrap() == ' '
        {
            self.position += 1;
        }
        let start = self.position;
        let mut value: i64 = 0;
        while self.position < self.expr.len()
            && self.expr.chars().nth(self.position).unwrap().is_digit(10)
        {
            let digit = self
                .expr
                .chars()
                .nth(self.position)
                .unwrap()
                .to_digit(10)
                .unwrap() as i64;
            value = value * 10 + digit;
            self.position += 1;
        }
        if start == self.position {
            return Err("expected number".to_string());
        }
        return Ok(value * sign);
    }
}

fn main() {
    let mut expr: String = String::new();
    std::io::stdin().read_line(&mut expr).unwrap();
    let right_brackets = expr.chars().filter(|&c| c == ')').count() as usize;
    let filling_brackets = "(".repeat(right_brackets) + &expr;
    let mut parser = Parser::new(filling_brackets);
    match parser.parse() {
        Ok(result) => println!("{}", result),
        Err(e) => println!("{}", e),
    }
}

题意简述

给定一个（中缀）表达式，求出它的值，保证运算结果及中间过程在 long long 范围内。

解法

众所周知，中缀表达式转后缀表达式方法如下：

遍历中缀表达式中的元素，

1. 遇到一个数，则输出该数；
2. 遇到左括号，则将其入栈；
3. 遇到右括号，不断取出栈顶并输出，直到栈顶为左括号，将左括号出栈；
4. 遇到运算符，只要栈顶符号的优先级不低于新符号（乘除>加减>左括号），取出栈顶并输出，最后将新符号入栈。

最后，依次取出并输出栈中所有剩余符号，输出序列就是一个与原表达式等价的后缀表达式。

求后缀表达式的值是容易的，或者我们可以在以上过程中直接求解。

但是，存在一些问题：

1. 数据存在负数，即一元负号运算符；
2. 数据存在乘幂运算符 ^，这个运算符是右结合（包括一元正负号运算符也是右结合的）的，以上给出的方法只解决左结合运算符；
3. 数据可能会出现多余括号情况。

对于问题一，我们可以在读入数字时考虑正负号，或者考虑将正负号标记为一元右结合运算符。对于后者，显然仅当上一个元素是左括号或其他二元运算符时会被标记。本篇题解采用后者。

对于问题二，有结论：在以上过程中，若遇到的运算符为右结合运算符，只需将情况 4 改为“只要栈顶符号的优先级低于新符号，取出栈顶并输出”。

对于问题三，由于过于简单，这里不再论述，详情参见代码。

AC Code

#include <bits/stdc++.h>
using namespace std;

bool delim(char c) { return c == ' '; }

bool is_op(char c) {
  return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

bool is_unary(char c) { return c == '+' || c == '-'; }

bool right_assoc(char c) { return c == -43 || c == -45 || c == '^'; }

int priority(char op) {
  switch (op) {
    case '+':
    case '-':
      return 1;
    case '*':
    case '/':
      return 2;
    case '^':
      return 4;
    case -43:
    case -45:
      return 3;
    default:
      return -1;
  }
}

long long qpow(long long a, long long b) {
  if (b < 0) return 0;
  if (b == 0) return 1;
  long long res = 1;
  for (; b > 0; b >>= 1) {
    if (b & 1) res *= a;
    a *= a;
  }
  return res;
}

void process_op(stack<long long>& st, char op) {
  if (op == '(') return;
  if (op < 0) {
    long long l = st.top();
    st.pop();
    switch (-op) {
      case '+':
        st.push(l);
        break;
      case '-':
        st.push(-l);
        break;
    }
  } else {
    long long r = st.top();
    st.pop();
    long long l = st.top();
    st.pop();
    switch (op) {
      case '+':
        st.push(l + r);
        break;
      case '-':
        st.push(l - r);
        break;
      case '*':
        st.push(l * r);
        break;
      case '/':
        if (r == 0) throw "division by zero";
        st.push(l / r);
        break;
      case '^':
        st.push(qpow(l, r));
        break;
    }
  }
}

long long evaluate(string& s) {
  stack<long long> st;
  stack<char> op;
  bool may_be_unary = true;
  for (int i = 0; i < (int)s.size(); i++) {
    if (delim(s[i])) continue;
    if (s[i] == '(') {
      op.push('(');
      may_be_unary = true;
    } else if (s[i] == ')') {
      while (!op.empty()) {
        char p = op.top();
        op.pop();
        if (p == '(') break;
        process_op(st, p);
      }
      may_be_unary = false;
    } else if (is_op(s[i])) {
      char cur_op = s[i];
      if (may_be_unary && is_unary(cur_op)) cur_op = -cur_op;
      while (
          !op.empty() &&
          ((!right_assoc(cur_op) && priority(op.top()) >= priority(cur_op)) ||
           (right_assoc(cur_op) && priority(op.top()) > priority(cur_op)))) {
        process_op(st, op.top());
        op.pop();
      }
      op.push(cur_op);
      may_be_unary = true;
    } else {
      long long num = 0;
      while (i < (int)s.size() && '0' <= s[i] && s[i] <= '9')
        num = (num * 10) + (s[i++] ^ '0');
      --i;
      st.push(num);
      may_be_unary = false;
    }
  }
  while (!op.empty()) {
    process_op(st, op.top());
    op.pop();
  }
  return st.top();
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  string ss;
  cin >> ss;
  try {
    cout << evaluate(ss) << "\n";
  } catch (const char* errorMsg) {
    cout << errorMsg << "\n";
  }
  return 0;
}

后记：关于 throw/try-catch 的解释

考虑到这玩意在 OI 界似乎不常见，这里解释一下，神犇请自行跳过。

简单来说，throw 可以抛出一个异常对象，这会使控制流沿调用栈向上（就是跳出当前函数/代码块），直到被 try-catch 捕获。若异常未被捕获，将调用 std::terminate，这将结束程序并返回一个非零值（通常似乎是 3）。

对于 try-catch 语句，当 try 块内抛出异常，会将异常对象与 catch 子句中声明的类型按顺序尝试匹配，特别地，catch(...) 可以捕获任何异常。

异常被捕获后，程序转入对应的 catch 块运行。

try-catch 的更多信息

好像也可以用 longjmp 函数实现类似效果，在 C 中可用。