第四章栈（2）

2. 一个算术表达式的后缀表达式形式如下：
op1 op2 operator
使用两个栈，一个用来存储操作数，另外一个用来存储操作符，设计并实现一个JavaScript函数，
该函数可以将中缀表达式转换为后缀表达式，然后利用栈对该表达式求值。
    考虑优先级：
        1.先乘除
        2.后加减
        3.有括号先算括号里
    

    基本思路：为了完成算术表达式的计算，用到了两个栈，一个用于存放操作数，另一个用于存放操作符。

    假设：程序中定义了两个栈:numStack(用来存放操作数)、operatorStack(用于存放操作符)。
    在处理操作数和操作符之前，首先将它们压入栈中。当要处理一个操作符时，从operatorStack中将它弹出，
    然后将它应用在来自numStack的前两个操作数上，得到的结果再压入numStack中。

实现的详细步骤：

    1.扫描阶段：程序从左到右扫描表达式，提取操作数、运算符和括号。
        1)如果提取的字符是一个操作数，将它压入numStack中。
        2)如果提取的字符是一个+或-的运算符，因为+、-运算符在算术表达式中的优先级是最低的，所以此时在将+或者-运算符插入栈中之前，可以处理operatorStack栈顶的所有运算符，最后将提取出来的运算符压入operatorStack中。
        3)如果提取的字符是一个*或/的运算符，则处理operatorStack栈顶的所有*和/的运算符，最后将新提取出来的运算符压入operatorStack中。
        4)如果提取出来的运算符是一个"("，则将它压入operatorStack中。
        5)如果提取出来的运算符是一个")"，则重复处理operatorStack栈顶的运算符，直到看到栈顶的运算符为")"。

    2.清除栈阶段：重复处理来自operatorStack栈顶的运算符，直到operatorStack为空为止。

function operatorCge(numStack,operatorStack) { let op1,op2,operator; op1=numStack.pop(); //取操作数的栈顶元素 op2=numStack.pop(); //取操作数的栈顶元素 operator=operatorStack.pop();//取操作符的栈顶元素 switch(operator) { case "+": numStack.push(parseFloat(op2)+parseFloat(op1)); //将字符串转换成数字 break; case "-": numStack.push(op2-op1); break; case "*": numStack.push(op2*op1); break; case "/": numStack.push(op2/op1); break; } } function evaluateExpression(str){ let numStack=new Stack(); //存放操作数 let operatorStack=new Stack();//存放运算符 str=str.split(""); for(let i=0;i<str.length;i++) { if(str[i].trim()=="") //如果字符串为空，则跳过此次循环 { continue; }else if(str[i].trim()=="+"||str[i].trim()=="-") { //如果字符串为“+”或“-”，则执行栈中已存数据的加减乘除 while(!operatorStack.isEmpty() && ( operatorStack.peek() == "+" || operatorStack.peek() == "-" || operatorStack.peek() == "*" || operatorStack.peek() == "/" )){ operatorCge(numStack,operatorStack); } operatorStack.push(str[i]); }else if(str[i].trim()=="*"||str[i].trim()=="/") { //如果字符串为“+”或“-”，则执行栈中已存数据的乘除计算 while(!operatorStack.isEmpty() && (operatorStack.peek() == "*" || operatorStack.peek() == "/" )){ operatorCge(numStack,operatorStack); console.log("*:",numStack.peek()); } operatorStack.push(str[i]); }else if(str[i].trim()=="(") { //如果遇到左括号，则将左括号压入操作符栈中 operatorStack.push(str[i]); }else if(str[i].trim()==")") { //如果遇到右括号，则计算栈中的数据，直到遇到左括号为止 while(operatorStack.peek()!="(") { operatorCge(numStack,operatorStack); } operatorStack.pop();//将进行过计算的左括号弹出 }else { //如果遇到的是操作数，则将操作数直接压入操作数栈中 numStack.push(str[i]); } } //对栈中数据进行计算，知道栈为空为止 while(!operatorStack.isEmpty()) { operatorCge(numStack,operatorStack); } return numStack.pop(); } let str="4+5-3*9-(2+ 3 )"; let result=evaluateExpression(str); console.log(result);//-23