逆波兰表达式求值

题目

根据逆波兰表示法, 求表达式的值. 注意两个整数之间的除法只保留整数部分.

题目保证给定的逆波兰表达式总是有效的, 换句话说, 表达式总会得出有效数值且不存在除数为 0 的情况.

示例

输入: tokens = ['2', '1', '+', '3', '*']
输出: 9
解释: 该算式转化为常见的中缀算术表达式为: (2 + 1) * 3 = 9

输入: tokens = ['4', '13', '5', '/', '+']
输出: 6
解释: 该算式转化为常见的中缀算术表达式为: 4 + 13 / 5 = 6

输入: tokens = ['10', '6', '9', '3', '+', '-11', '*', '/', '*', '17', '+' ,'5' ,'+']
输出: 22
解释: 该算式转化为常见的中缀算术表达式为:
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

题解

逆波兰表达式是一种后缀表达式, 所谓后缀就是指算符写在后面.

• 平常使用的算式则是一种中缀表达式, 如 (1 + 2) * (3 + 4)
• 该算式的逆波兰表达式写法为 ( 1 2 + ) ( 3 4 + ) * )

解决方法就是遇见数字就 push 到栈, 遇到符号就取栈顶两个数字(一定有)进行运算.

JavaScript

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function (tokens) {
  const stack = []

  for (const token of tokens) {
    if (isNaN(token)) {
      const a = stack.pop()
      const b = stack.pop()
      stack.push(calc(token, a, b))
    } else {
      // 注意题目给的是数字字符串, 记得先转成数字再推入栈中
      stack.push(+token)
    }
  }

  return stack[0]
}

var calc = function (operator, a, b) {
  const rules = {
    '+': b + a,
    '-': b - a,
    '*': b * a,
    '/': (b / a) | 0,
  }

  return rules[operator]
}

Rust

用 rust 实现这道题不难, 但灵活使用 match 会使代码很性感.

pub fn eval_rpn(tokens: Vec<String>) -> i32 {
    let mut stack = vec![];

    #[inline]
    fn calc(operator: &str, a: i32, b: i32) -> i32 {
        match operator {
            "*" => b * a,
            "/" => b / a,
            "+" => b + a,
            _ => b - a,
        }
    }

    for token in tokens.iter() {
        match token.parse::<i32>() {
            Ok(num) => stack.push(num),
            Err(_) => {
                let a = stack.pop().unwrap();
                let b = stack.pop().unwrap();
                stack.push(calc(operator, a, b));
            }
        }
    }

    stack[0]
}