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