题解 | #表达式求值#

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

let operator = '+-*/)';
let dataStack = new Array(); // 记录运算数字
let operatorStack = new Array(); // 记录运算符号



function compareOperator(topOperator, currentOperator) { // 比较运算符优先级
    if(topOperator === '(') { // 括号优先级最高
        return false;
    }else if((topOperator === '+' || topOperator === '-') && (currentOperator === '*' || currentOperator === '/')) { // 加减小于乘除
        return false;
    }
    return true;
}

function doCalculate(){
    let secondData = dataStack.pop();
    let firstData = dataStack.pop();
    let result = 0;

    let operator = operatorStack.pop();
    switch(operator) {
        case '+':
            result = firstData + secondData;
            break;
        case '-':
            result = firstData - secondData;
            break;
        case '*':
            result = firstData * secondData;
            break;
        case '/':
            result = firstData / secondData;
            break;
    }

    dataStack.push(result);
}

function resolveExpression(inputStr) {
    dataStack = []; //记录运算数字
    operatorStack = []; //记录运算符

    operatorStack.push('('); //整个运算式添加括号
    inputStr += ')';

    let nextIsOperator = false;
    for(let index = 0; index < inputStr.length; index++) {
        
        if(inputStr[index] === '(') //如果是左括号都在运算符栈加入(
        {
            operatorStack.push('(');
        }
        else if(inputStr[index] === ')')  //遇到右括号
        {
            while(operatorStack[operatorStack.length -1] !== '('){ //弹出开始计算直到遇到左括号
                doCalculate();
            }
            operatorStack.pop();
        }
        else if(nextIsOperator) 
        {
            while(compareOperator(operatorStack[operatorStack.length -1], inputStr[index])){//比较运算优先级
                doCalculate();
            }
            operatorStack.push(inputStr[index]); //需要将现阶段加入栈中等待运算
            nextIsOperator = false;
        }else { //数字
            let numberIndex = index; //记录起始
            if(inputStr[numberIndex] === '-' || inputStr[numberIndex] === '+') { //正负号
                index++;
            }

            while(!operator.includes(inputStr[index])) {
                index++;
            }
           
            let number = inputStr.substr(numberIndex, index-numberIndex);
            dataStack.push(parseInt(number));  //截取数字部分，转数字
            index--;
            nextIsOperator = true;//数字结束，下一次flag为true就是运算符了
        }
    }
    console.log(dataStack[dataStack.length-1]);
}


void async function () {
    // Write your code here
    while(line = await readline()){
        // 方法1：写完给面试官一个大逼兜
        // console.log(eval(line))

        // 方法2：运算式可以看成运算式的子问题，因此可以用递归解决
        // 方法3：双栈法
        resolveExpression(line.trim())
    }
}()