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

我们平常所碰见的算术表达式如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.