后缀表达式求值

Leetcode 第150题 150逆波兰表达式求值
思路
建立一个用于存数的栈，逐一扫描后缀表达式中的元素

  • 如果遇到一个数，则把改数入栈
  • 如果遇到运算符，就取出栈顶的两个数进行计算，然后把结果入栈

扫描完成后，栈中恰好剩一个数，就是后缀表达式的值

  1. /**
  2.  * @param {string[]} tokens
  3.  * @return {number}
  4.  */
  5.  var evalRPN = function(tokens) {
  6.     let stack=[]
  7.     for(token of tokens){
  8.         if(token === "+" ||token==="-"||token==="*"|| token==="/"){
  9.             let y=stack.pop()
  10.             let x=stack.pop()
  11.             let z=calc(x,y,token)
  12.             stack.push(z)
  13.         }else{
  14.             stack.push(parseInt(token))
  15.         }
  16.     }
  17.     return stack[0]
  18. };
  19. var calc=function(x,y,op){
  20.     if(op==="+") return x+y
  21.     if(op==="-") return x-y
  22.     if(op==="*") return x*y
  23.     if(op==="/") return parseInt(x / y, 10);
  24.     return 0
  25. }

中缀表达式求值

leetcode第227题 227. 基本计算器 II
思路
先将中缀表达式转换为后缀表达式。建立一个用于存运算符的栈，逐一扫描中缀表达式中的元素

  • 遇到一个数，输出该数
  • 遇到运算符，只要栈顶符号的优先级>=新符号，就不断取出栈顶并输出，最后把新符号入栈。优先级顺序为乘除号>加减号>
  • 依次取出并输出栈中的所有剩余符合

最终输出一个后缀表达式 然后调用上一题实现的函数

  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  6. var evalRPN = function (tokens) {
  7.   let stack = [];
  8.   for (token of tokens) {
  9.     if (token === "+" || token === "-" || token === "*" || token === "/") {
  10.       let y = stack.pop();
  11.       let x = stack.pop();
  12.       let z = calc(x, y, token);
  13.       stack.push(z);
  14.     } else {
  15.       stack.push(parseInt(token));
  16.     }
  17.   }
  18.   return stack[0];
  19. };
  20. var calc = function (x, y, op) {
  21.   if (op === "+") return x + y;
  22.   if (op === "-") return x - y;
  23.   if (op === "*") return x * y;
  24.   if (op === "/") return parseInt(x / y, 10);
  25.   return 0;
  26. };
  27. var calculate = function (s) {
  28.   s += " ";//处理表达式是数字结尾的情况
  29.   let num = "";
  30.   let stack = [];//保存运算符
  31.   let list = [];//后缀表达式
  32.   for (let ch of s) {
  33.     if (ch >= "0" && ch <= "9") {
  34.       num += ch;
  35.       continue;
  36.     } else {
  37.       if (num.length != 0) {
  38.         list.push(num);
  39.         num = "";
  40.       }
  41.     }
  42.     if (ch === " ") continue;
  43.     let currRank = getRank(ch);
  44.     while (stack.length != 0 && getRank(stack[stack.length - 1]) >= currRank) {
  45.       list.push(stack.pop());
  46.     }
  47.     stack.push(ch);
  48.   }
  49.   while (stack.length != 0) {
  50.     list.push(stack.pop());
  51.   }
  52.   return evalRPN(list)
  53. };
  55. var getRank = (ch) => {
  56.   if (ch === "*" || ch === "/") return 2;
  57.   if (ch === "+" || ch === "-") return 1;
  58.   return 0;
  59. };