首页 > 代码库 > 使用栈结构完成四则运算
使用栈结构完成四则运算
使用栈结构完成四则运算
思路:
0.初始化 a.操作栈,b.数字栈 ,定义优先级 +:1 , - : 1 , * : 2 , / : 2
1.如果是数字入数字栈
2.如果是左括号,入操作栈
3.如果右括号:
while(操作栈顶元素 != 左括号){
//----计算过程
num1 = 弹出操作数;
num2 = 弹出操作数;
var op = 弹出操作符;
var r = eval(num2 + op+ num1 );//注意顺序,而不是eval(num1 + op + num2) ,其中,使用了JS中的eval来完成脚本解析和动态执行,这部分不同语言实现会略有不同
计算结果r进入数字栈
//----
}
4.如果是其它操作符 (+-*/) :
a.得到当前优先级 ,得到操作栈栈顶元素优先级
b.如果操作栈空或栈顶元素优先级 < 当前优先级 ,注意是小于,而不是小于等于: 直接入操作栈;
c.否则,,
while(栈顶元素优先级>=当前元素优先级p1){
//--计算过程--
}
while(循环操作栈还有元素){
//--计算过程
}
以下是JS实现:
Array.prototype.select = function (f){ var arr = new Array(); for(var i = 0;i < this.length;i++){ arr.push(f(this[i])); } return arr; }; var op = [{k:‘+‘,w:1},{k:‘-‘,w:1},{k:‘*‘,w:2},{k:‘/‘,w:2},{k:‘(‘,w:0.5},{k:‘)‘}] var opIndex = function(c){ for(var j = 0; j < op.length; j++){ if(op[j].k == c){return j;} } return -1; } var isNum = function(c){ return parseInt(c) == c; } function p(str){ var retArr = new Array(); var numStr = ""; for(var i = 0;i < str.length;i++){ if(str[i] == ‘ ‘){continue;} else if(isNum(str[i])){ numStr += str[i]; if(i == str.length - 1){ retArr.push(numStr); break; } } else if(opIndex(str[i]) > -1 ){ if(numStr != ""){ retArr.push(numStr); } retArr.push(str[i]); numStr = ""; } else{ console.log("error : unexpected char " + str[i] + ", only [0-9] and [+-*/()] is supported"); return null; } } return retArr; } function c(arr){ var ret = new Array(); var opArr = new Array(); var calc = function(){ var num1 = ret.pop(); var num2 = ret.pop(); var opr = opArr.pop(); ret.push(eval(‘(‘+num2+‘)‘+opr.k+‘(‘+num1+‘)‘)); } for(var i = 0;i < arr.length; i++){ if(isNum(arr[i])){ ret.push(arr[i]); continue; } if(arr[i] == ‘(‘){ opArr.push({k:‘(‘,w:0.5}); continue; } if(arr[i] == ‘)‘){ for(;opArr[opArr.length-1].k!=‘(‘;){ calc(); } opArr.pop(); continue; } var index = opIndex(arr[i]); var weight = op[index].w; if(opArr.length == 0 || opArr[opArr.length-1].w < weight /*note , should not ‘<=‘ */){ opArr.push({k:arr[i],w:weight}); } else{ for(;opArr.length > 0 && opArr[opArr.length-1].w >= weight;){ calc(); } opArr.push({k:arr[i],w:weight}); } } for(;opArr.length > 0;){ calc(); } return ret; } var arr = p("5-4+6*(7-10)"); console.log(c(arr));
注:代码中的Array.prototype.select扩展函数是为了方便debug定义的。
使用栈结构完成四则运算
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。