美文网首页
javascript中逆波兰式的转化及求值

javascript中逆波兰式的转化及求值

作者: 王伯卿 | 来源:发表于2018-01-27 15:50 被阅读0次

    我们平常所碰见的算术表达式如1+2+3,叫做中缀表达式.
    如果要将他转危为逆波兰式(也叫后缀表达式),那就应该是12+3+
    这篇文章主要讲如何将中缀表达式转化为后缀表达式并且求值

    转化

    我们假设用户输入了一个正确格式的算术表达式
    这个表达式可以带小数,可以有小括号,支持加减乘除
    本文不涉及判断用户是否输入了合法的表达式,默认接收到的表达式都是合法的.
    另外,我们需要先将用户输入的字符串,根据数字,运算符号,分隔成一个个的数组元素,便于转化的时候从左至右扫描,这边使用了正则表达式来解决这个问题.

    思路:

    1.初始化两个栈,一个output,一个operator
    2.从左到右扫描数组
    3.如果是数字,直接入栈output
    4.如果是操作符加减乘除
    4-1.判断如果operator为空,直接入栈operator
    4-2.操作符优先级比栈顶元素高,直接入栈operator
    4-3.栈顶元素为左括号 '(',直接入栈operator
    4-4.否则弹出operator栈顶元素,入栈output,转回4-1再次判断,直至入栈operator为止
    5.如果是括号
    5-1.如果是左括号,直接入栈
    5-2.如果是右括号,弹出operator栈顶元素,入栈output,直到栈顶元素为左括号,并且将该栈顶元素舍弃
    6.判断operator栈是否为空,如果不为空,依次弹出栈顶元素,入栈output

    求值

    1.声明一个栈
    2.从左到右依次扫描后缀表达式
    3.如果是数字,直接入栈
    4.如果是操作符号,栈顶依次弹出两个数字,计算值之后,然后入栈
    5.直到后缀表达式的最后一个操作符

    //判断是否是运算符
    //如果是运算符加减乘除,isOperator就会返回true,否则就会返回false
    var isOperator=function(operator){
      return(operator=='+'||operator=='-'||operator=='*'||operator=='/');
    };
    
    //判断是否是数字
    //即使是字符串也没有关系,isNaN会自动帮我们处理
    var isNumber=function(num){
      //isNaN=is not a number
      //所以前面要有一个!表示否定,说明是数字
      return(!isNaN(num));
    };
    
    //比较运算符的优先级
    var priorityCompare=function(op1,op2){
      //op1=op2 返回0
      //op1>op2 返回1
      //op1<op2 返回-1
      switch(op1){
        //如果op1是'+'或者'-'的情况
        case '+': case '-':
          //如果op2是'*'或者'/'是true的话,则返回-1,说明优先级比op2小
          //否则返回0
          //如果返回0,证明op2是'+'或者'-',说明优先级相同
          return(op2=='*'||op2=='/'?-1:0);
        //如果op1是'*'或者'/'的情况
        case '*': case '/':
          //如果op2是'+'或者'-'是true的话,则返回1,说明优先级比op2大
          //否则返回0
          //如果返回0,证明op2是'*'或者'/',说明优先级相同
          return(op2=='+'||op2=='-'?1:0);
      }
      return 1;
    };
    
    //利用正则表达式将运算表达式字符串转换为数组
    var stringToArray=function(str){
      //这里用到match方法
      //match接受一个正则表示做参数
      //需要用两个斜线'/'把正则表达式括起来
      //g表示全局搜索
      //match方法返回一个数组
      var result=str.match(/[\+\-\*/()]|\d+(\.\d+)?/g)
      return result;
    };
    
    //判断数字是否为空
    //是空返回true
    //不是空返回false
    var isEmpty=function(calArr){
      if(calArr.length==0){
        return true;
      }else{
        return false;
      }
    };
    
    //将中缀表达式转化为逆波兰表达式
    var toReversePolishNotation=function(arr){
      //操作符栈
      var operatorArr=[];
      //数字栈
      var output=[];
      //栈顶元素的标号
      var topOfTheStack;
      for(i=0;i<arr.length;i++){
        var str=arr[i];
        //如果是数字,输出
        if(isNumber(str)){
          output.push(str);
        //如果是操作符加减乘除
        }else if(isOperator(str)){
          topOfTheStack=operatorArr.length-1;
          //如果栈不为空且栈顶元素不是'('且优先级小于等于栈顶元素为true
          //则依次弹出栈顶元素输出
          //直到栈为空或者栈顶元素不是'('或者优先级大于栈顶元素
          while(!isEmpty(operatorArr)
                &&operatorArr[topOfTheStack]!='('
                &&priorityCompare(str,operatorArr[topOfTheStack])<=0){
            var tempChar=operatorArr.pop();
            output.push(tempChar);
            topOfTheStack=operatorArr.length-1;
          }
          //栈顶为空,或者栈顶元素是'(',或者优先级比栈顶元素大,那就直接入栈
          operatorArr.push(str);
        }else if(str=='('){
          //如果是左括号就直接入栈
          operatorArr.push(str);
        }else if(str==')'){
          topOfTheStack=operatorArr.length-1;
          //如果是右括号就需要依次弹出栈顶元素输出,直至栈顶元素为左括号,此时跳出循环
          while(operatorArr[topOfTheStack]!='('){
            output.push(operatorArr.pop());
            topOfTheStack=operatorArr.length-1;
          }
          //跳出循环到此处,讲左括号舍弃
          operatorArr.pop();
        }else{
          //如果发现奇怪的东西则输出error
          console.log(str+'error');
        }
      }
      //最后如果栈中还有操作符则依次弹出输出
      while(!isEmpty(operatorArr)){
        output.push(operatorArr.pop());
      }
      //返回该输出供最后计算使用
      return output;
    };
    
    //计算后缀表达式
    var cal=function(array){
      var calOutput=[];
      //从左到右读取数组中的每个值
      //如果是数字直接入栈
      //如果是操作符,则从栈中依次弹出两个数,计算好结果后,再入栈
      for(i=0;i<array.length;i++){
        //如果是数字直接输出
        if(isNumber(array[i])){
          calOutput.push(array[i]);
        }else if(isOperator(array[i])){
          //如果不是数字,那就肯定是操作符
          //这里需要把字符串转化成数字
          var num1=parseFloat(calOutput.pop());
          var num2=parseFloat(calOutput.pop());
          var num3;
          switch(array[i]){
            case '+':
              num3=num1+num2;
              calOutput.push(num3);
              break;
            case '*':
              num3=num1*num2;
              calOutput.push(num3);
              break;
            case '-':
              num3=num2-num1;
              calOutput.push(num3);
              break;
            case '/':
              num3=num2/num1;
              calOutput.push(num3);
              break;
          }
        }else{
          console.log(array[i]+'error');
        }
      }
      //最后输出中会有一个结果,就是计算结果
      return calOutput;
    };
    

    自己测试了很多遍,没有发现bug.

    相关文章

      网友评论

          本文标题:javascript中逆波兰式的转化及求值

          本文链接:https://www.haomeiwen.com/subject/nxbnaxtx.html