题解 | #49.表达式求值#

将中缀表达式化为逆波兰表达式

借助两个栈，一个存放数字，一个存放操作符

思路：

初始化：

• 将运算符加入到map里面，设定优先级，注意(的优先级最低
• 将字符串的空格删除

遍历字符串：

• 数字：加入数组，注意数字可能占多位
• 左括号：直接push到ops栈
• 右括号：从nums栈pop两个数字，进行运算，运算的结果push回nums栈，直至碰到(
• 其他运算符：
  1. 如果当前运算符的优先级$\le \backslash leq$ops的最后一个，一直运算(例子：5*2+3，碰到+的时候计算5*2)
  2. 如果当前运算符的$>>$ops的最后一个，将运算符push到ops(例子：5+2*3，碰到*的时候将*push到ops栈)

注意：

• 必须$\le \backslash leq$才可以，不可以是<,比如1-2-3，如果碰到第二个减法依然不进行运算，那么之后回进行2-3的运算，出现错误

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 返回表达式的值
 * @param s string字符串 待计算的表达式
 * @return int整型
 */
function solve( s ) {
  let nums = [];
  let ops = [];
  let map = new Map();
  
  //初始化函数，设定运算符优先级，把字符串中的空格去除
  function init(){
    map.set('(', -1);
    map.set('+',1);
    map.set('-',1);
    map.set('*',2);
    s = s.replace(' ','');
  }
  
  function calc(){
    let right = nums.pop();
    let left = nums.pop();
    let sign = ops.pop();
    switch(sign){
        case'+':nums.push(left+right);break;
        case'-':nums.push(left-right);break;
        case'*':nums.push(left*right);break;
        case'/':nums.push(left/right);break;
    }
  }
    
    init();
    let i = 0;
    while(i<s.length){
      if( s[i]>='0' && s[i]<='9'  ){//处理数字
        let value = 0;
        while( s[i]>='0' && s[i]<='9' ){
          value = value*10 + parseInt(s[i]);
          i++;
        }
        nums.push(value);
      }else if( s[i]=='(' ){//碰到左括号近栈
        ops.push('(');
        i++;
      }else if( s[i]==')' ){//计算到最近的一个左括号为止
        while( ops[ops.length-1] != '(' ){
          calc();
        }
        ops.pop();//把左括号弹出
        i++;
      }else{//运算符
        if(ops.length==0){//栈为空时，遇到运算符，直接入栈
          ops.push( s[i] );
        }else if( map.get(s[i]) > map.get( ops[ops.length-1] ) ){//当前运算符优先级高于之前的  5+2*3
          ops.push( s[i] );
        }else{//当前运算符优先级<=之前的  5*2-3
          do{
            calc();
          }while( map.get(s[i]) <= map.get( ops[ops.length-1] ) );
          ops.push( s[i] );
        }
        i++;
      }
    }
    while(ops.length)
      calc();
  return nums[0];
}