中缀表达式转后缀表达式(用于求字符串表达式值)(js栈和队列的实现是通过数组的push和unshift方法插值,pop方法取值)

中缀表达式:就是我通常用的算术或逻辑公式;

后缀表达式:不包含括号,运算符放在两个运算对象后面,所有的计算按运算符出现的顺序,严格从左向右进行,不用考虑运算符优先级;

如,(2+1)*3 转换后,2 1 + 3 *

1、人工实现转换

如中缀表达式:a+b*c-(d+e)

  (1)、按照运算符优先级对所有运算单位加括号,式子变成:((a+(b*c))-(d+e))

  (2)、把运算符号移动到对应括号后面,变成:((a(bc)*)+(de)+)-

  (3)、把括号去掉就变成后缀表达式了:abc*+de+-

2、中缀转后缀算法:

如中缀表达式:(1+2)*((8-2)/(7-4))

  (1)、设立一个空栈,用于存放运算符

  (2)、从左向右扫描,如果是操作数,直接输出;如果遇到左括号直接进栈,如果遇到右括号,则一直退栈,直到遇到左括号;如果是运算符,要和栈顶运算符比较(此处运算符比较就是+、-、*、/四则运算比较),比栈*别高,进栈,否则输出栈顶运算符(比较一次),然后运算符进栈

  (3)、如果栈中剩有运算符,则依序出栈

例子:

//        var expression = '(1+2)*((8-2)/(7-4))';
var expression ='3+(2-5)*6/3'
var obj = {'+': 0, '-': 0, '*': 1, '/': 1, '(': -1};
var arr = [];
var str = '';
for (var i = 0; i < expression.length; i++) {
var curChar = expression[i];
if (curChar == ' ') {
continue;
}
var num = /^\d$/.test(curChar);
if (num) {
str = str + curChar + ' ';
continue;
} else if (curChar == '(') {
arr.push(curChar);
} else if (curChar == ')') {
var len = arr.length;
for (var j = 0; j < len; j++) {
var pop = arr.pop();
if (pop != '(') {
str = str + pop + ' ';
} else {
break;
}
}
} else {
if (arr.length > 0) {
var top = arr[arr.length - 1];
if (obj[curChar] > obj[top]) {
arr.push(curChar);
} else {
var pop = arr.pop();
arr.push(curChar);
str = str + pop + ' ';
}
} else {
arr.push(curChar);
}
}
}
for(var i=arr.length-1;i>=0;i--){
str = str + arr[i] + ' ';
}
console.log(str);

中缀转后缀

3、后缀表达式求职算法

  (1)、设定一个空栈

  (2)、从左向右扫描后缀表达式

  (3)、如果是操作数入栈,如果是运算符,从栈中取出两个数,进行运算(如果使用js数组,pop方法弹栈,那么将先出的放在运算符右边,后出的在左边),再将结果入栈

直到后缀表达式扫描完毕,栈中仅有一个元素,即为运算结果

依然使用上面的表达式,console.log(calculatePostfix(str));

function calculatePostfix(postfixExp) {
var arr = [];
for (var i = 0; i < postfixExp.length; i++) {
var curVal = postfixExp[i];
if(curVal==' '){
continue;
}
switch (curVal) {
case '+':
{
var pop1 = arr.pop();
var pop2 = arr.pop();
var res=parseFloat(pop2)+parseFloat(pop1);
arr.push(res);
break;
}
case '-':
{
var pop1 = arr.pop();
var pop2 = arr.pop();
var res=parseFloat(pop2)-parseFloat(pop1);
arr.push(res);
break;
}
case '*':
{
var pop1 = arr.pop();
var pop2 = arr.pop();
var res=parseFloat(pop2)*parseFloat(pop1);
arr.push(res);
break;
}
case '/':
{
var pop1 = arr.pop();
var pop2 = arr.pop();
var res=parseFloat(pop2)/parseFloat(pop1);
arr.push(res);
break;
}
default :
{
arr.push(curVal);
break;
}
}
}
return arr[0];
}

后缀表达式运算

上一篇:使用NSSM把.Net Core部署至 Windows 服务


下一篇:【flex弹性盒布局】------这个强大的功能