0150. 逆波兰表达式求值 Evaluate Reverse Polish Notation

问题描述

这个问题是解析后缀表达式, 可以用栈来完成.

但要注意操作符对应的左右两侧的数值顺序.

代码实现

Rust

#![allow(unused)]
fn main() {
// Stack
// 后缀表达式
// - 优化模式匹配
// - 优化出栈操作
pub fn eval_rpn2(tokens: Vec<String>) -> i32 {
    let mut stack: Vec<i32> = Vec::with_capacity(tokens.len());

    for token in tokens.iter() {
        match token.as_str() {
            // 匹配运算符.
            "+" => {
                debug_assert!(stack.len() >= 2);
                let num1 = stack.pop().unwrap();
                let num2 = stack.last_mut().unwrap();
                *num2 += num1;
            }
            "-" => {
                debug_assert!(stack.len() >= 2);
                let num1 = stack.pop().unwrap();
                let num2 = stack.last_mut().unwrap();
                *num2 -= num1;
            }
            "*" => {
                debug_assert!(stack.len() >= 2);
                let num1 = stack.pop().unwrap();
                let num2 = stack.last_mut().unwrap();
                *num2 *= num1;
            }
            "/" => {
                debug_assert!(stack.len() >= 2);
                let num1 = stack.pop().unwrap();
                let num2 = stack.last_mut().unwrap();
                *num2 /= num1;
            }
            num_str => {
                //let num: i32 = i32::from_str(num_str).unwrap();
                //let num: i32 = i32::from_str_radix(num_str, 10).unwrap();
                let num: i32 = num_str.parse().unwrap();
                stack.push(num);
            }
        }
    }
    // 栈顶的元素就是计算结果.
    stack.pop().unwrap()
}
}

C++

#include <cassert>

#include <stack>
#include <string>
#include <vector>

int evalRPN(std::vector<std::string>& tokens) {
  std::stack<int> stack;

  for (const std::string& token : tokens) {
    if (token == "+") {
      const int num1 = stack.top();
      stack.pop();
      const int num2 = stack.top();
      stack.pop();
      const int num = num2 + num1;
      stack.push(num);
    } else if (token == "-") {
      const int num1 = stack.top();
      stack.pop();
      const int num2 = stack.top();
      stack.pop();
      const int num = num2 - num1;
      stack.push(num);
    } else if (token == "*") {
      const int num1 = stack.top();
      stack.pop();
      const int num2 = stack.top();
      stack.pop();
      const int num = num2 * num1;
      stack.push(num);
    } else if (token == "/") {
      const int num1 = stack.top();
      stack.pop();
      const int num2 = stack.top();
      stack.pop();
      const int num = num2 / num1;
      stack.push(num);
    } else {
      const int num = std::stoi(token);
      stack.push(num);
    }
  }

  // 栈顶的元素就是计算结果.
  return stack.top();
}

void check_solution() {
  std::vector<std::string> tokens = {"4","13","5","/","+"};
  const int ret = evalRPN(tokens);
  assert(ret == 6);
}

int main() {
  check_solution();
  return 0;
}