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

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

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),
    }
}