【JS】用调度场算法计算表达式的值,javascript实现

用调度场算法计算表达式的值,javascript实现

卡德加发布于 6 分钟前

最近想试下做微信小程序,刚开始写,想找点东西练手,试下写个计算器的小程序,查了一下,做表达式求值是用的Dijkstra的调度场算法,用两个栈就可以实现,一个输出栈,一个操作符栈,算法描述如下:

  • 依次按顺序读入,
  • 读到数字:直接输出;
  • 读到一般运算符:如果栈顶的运算符优先级不低于该运算符,则输出栈顶运算符并使之出栈,直到栈空或不满足上述条件为止;然后入栈;
  • 读到左括号:直接入栈;
  • 读到右括号:输出栈顶运算符并使之出栈,直到栈顶为左括号为止;令左括号出栈。
  • 当读入完毕时,依次输出并弹出栈顶运算符,直到栈被清空。

这里我写的比较简单,详细大家可以看以下这篇知乎上的文章:
https://zhuanlan.zhihu.com/p/...
以下是我用javascript实现的代码,加了一点自己的东西,也就是字符串转换成分解好的数组的代码,在node.js上运行通过。

function cal(strArr){

let first={'+':1,'-':1,'*':2,'/':2,'sqrt':3,'sin':3,'cos':3}

let opStack=[];

let outputStack=[];

let calStack=[];

for(let i=0;i<strArr.length;i++){

let s=strArr[i];

if(!isNaN(s)){

outputStack.push(s);

}else{

if(s == '(')opStack.push(s);

else if (s == ')'){

while((topOp=opStack.pop()) != '('){

outputStack.push(topOp);

}

}else{

if(opStack.length == 0){

opStack.push(s)

}else{

let topOp=opStack[opStack.length-1];

while(first[topOp] >= first[s]){

outputStack.push(opStack.pop());

if(opStack.length == 0)break;

topOp=opStack[opStack.length-1];

}

opStack.push(s)

}

}

}

}

while(opStack.length > 0)outputStack.push(opStack.pop())

for(let i=0;i<outputStack.length;i++){

let s=outputStack[i];

if(!isNaN(s))calStack.push(s);

else {

let r=Number(calStack.pop());

let v=0;

if(s== '+')v=Number(calStack.pop())+r;

else if(s=='-')v=Number(calStack.pop())-r;

else if(s=='*')v=Number(calStack.pop())*r;

else if(s== '/')v=Number(calStack.pop())/r;

else if(s == 'sqrt')v=Math.sqrt(r)

else if(s == 'sin')v=Math.sin(r)

else if(s == 'cos')v=Math.cos(r)

calStack.push(v);

}

}

return calStack.pop();

}

//计算字符串按数字和操作符分解转换成数组

function str2arr(str){

let resultArr=[];

const symbolSet=['+','-','*','/','(',')','sqrt','sin','cos','log']

let currentStr=''

for (let s of str){

if(symbolSet.indexOf(s) > -1){

if(currentStr != '')resultArr.push(currentStr);

resultArr.push(s)

currentStr='';

}else{

if(s == '.'){

currentStr=currentStr+s

}else{

let currentStrType= isNaN(currentStr)

let sType=isNaN(s)

if(sType == currentStrType){

currentStr=currentStr+s

}else{

if(currentStr != '')resultArr.push(currentStr)

currentStr=s

}

}

}

}

if(currentStr != '')resultArr.push(currentStr)

//检查括号,左括号进栈,右括号出栈,最后栈必须为空

//检查数字

let bracketsStack=[]

for(let i=0;i<resultArr.length;i++){

if(symbolSet.indexOf(resultArr[i]) > -1){

if(resultArr[i] == '(')bracketsStack.push(resultArr[i])

else if(resultArr[i] == ')'){

if(bracketsStack.length == 0)return {result:false,msg:'括号错误',data:resultArr};

bracketsStack.pop()

}

}else if (isNaN(resultArr[i])) return {result:false,msg:'字符串错误',data:resultArr};

}

if(bracketsStack.length > 0) return {result:false,msg:'括号错误',data:resultArr};

return {result:true,msg:'转换成功',data:resultArr};

}

let str="1-sin(2)*3.14/5"

let {result,msg,data}=str2arr(str)

if(result == true){

console.log(data)

let calResult=cal(data)

console.log(calResult)

}else console.log(msg)

console.log(1-Math.sin(2)*3.14/5)

以上代码我亲测可用,有写的不好的地方,欢迎大家点评。

javascript算法-数据结构

阅读 9发布于 6 分钟前

本作品系原创,采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议

avatar

卡德加

php程序员

9 声望

0 粉丝

0 条评论

得票时间

avatar

卡德加

php程序员

9 声望

0 粉丝

宣传栏

最近想试下做微信小程序,刚开始写,想找点东西练手,试下写个计算器的小程序,查了一下,做表达式求值是用的Dijkstra的调度场算法,用两个栈就可以实现,一个输出栈,一个操作符栈,算法描述如下:

  • 依次按顺序读入,
  • 读到数字:直接输出;
  • 读到一般运算符:如果栈顶的运算符优先级不低于该运算符,则输出栈顶运算符并使之出栈,直到栈空或不满足上述条件为止;然后入栈;
  • 读到左括号:直接入栈;
  • 读到右括号:输出栈顶运算符并使之出栈,直到栈顶为左括号为止;令左括号出栈。
  • 当读入完毕时,依次输出并弹出栈顶运算符,直到栈被清空。

这里我写的比较简单,详细大家可以看以下这篇知乎上的文章:
https://zhuanlan.zhihu.com/p/...
以下是我用javascript实现的代码,加了一点自己的东西,也就是字符串转换成分解好的数组的代码,在node.js上运行通过。

function cal(strArr){

let first={'+':1,'-':1,'*':2,'/':2,'sqrt':3,'sin':3,'cos':3}

let opStack=[];

let outputStack=[];

let calStack=[];

for(let i=0;i<strArr.length;i++){

let s=strArr[i];

if(!isNaN(s)){

outputStack.push(s);

}else{

if(s == '(')opStack.push(s);

else if (s == ')'){

while((topOp=opStack.pop()) != '('){

outputStack.push(topOp);

}

}else{

if(opStack.length == 0){

opStack.push(s)

}else{

let topOp=opStack[opStack.length-1];

while(first[topOp] >= first[s]){

outputStack.push(opStack.pop());

if(opStack.length == 0)break;

topOp=opStack[opStack.length-1];

}

opStack.push(s)

}

}

}

}

while(opStack.length > 0)outputStack.push(opStack.pop())

for(let i=0;i<outputStack.length;i++){

let s=outputStack[i];

if(!isNaN(s))calStack.push(s);

else {

let r=Number(calStack.pop());

let v=0;

if(s== '+')v=Number(calStack.pop())+r;

else if(s=='-')v=Number(calStack.pop())-r;

else if(s=='*')v=Number(calStack.pop())*r;

else if(s== '/')v=Number(calStack.pop())/r;

else if(s == 'sqrt')v=Math.sqrt(r)

else if(s == 'sin')v=Math.sin(r)

else if(s == 'cos')v=Math.cos(r)

calStack.push(v);

}

}

return calStack.pop();

}

//计算字符串按数字和操作符分解转换成数组

function str2arr(str){

let resultArr=[];

const symbolSet=['+','-','*','/','(',')','sqrt','sin','cos','log']

let currentStr=''

for (let s of str){

if(symbolSet.indexOf(s) > -1){

if(currentStr != '')resultArr.push(currentStr);

resultArr.push(s)

currentStr='';

}else{

if(s == '.'){

currentStr=currentStr+s

}else{

let currentStrType= isNaN(currentStr)

let sType=isNaN(s)

if(sType == currentStrType){

currentStr=currentStr+s

}else{

if(currentStr != '')resultArr.push(currentStr)

currentStr=s

}

}

}

}

if(currentStr != '')resultArr.push(currentStr)

//检查括号,左括号进栈,右括号出栈,最后栈必须为空

//检查数字

let bracketsStack=[]

for(let i=0;i<resultArr.length;i++){

if(symbolSet.indexOf(resultArr[i]) > -1){

if(resultArr[i] == '(')bracketsStack.push(resultArr[i])

else if(resultArr[i] == ')'){

if(bracketsStack.length == 0)return {result:false,msg:'括号错误',data:resultArr};

bracketsStack.pop()

}

}else if (isNaN(resultArr[i])) return {result:false,msg:'字符串错误',data:resultArr};

}

if(bracketsStack.length > 0) return {result:false,msg:'括号错误',data:resultArr};

return {result:true,msg:'转换成功',data:resultArr};

}

let str="1-sin(2)*3.14/5"

let {result,msg,data}=str2arr(str)

if(result == true){

console.log(data)

let calResult=cal(data)

console.log(calResult)

}else console.log(msg)

console.log(1-Math.sin(2)*3.14/5)

以上代码我亲测可用,有写的不好的地方,欢迎大家点评。

以上是 【JS】用调度场算法计算表达式的值,javascript实现 的全部内容, 来源链接: www.h5w3.com/113131.html

回到顶部