javascript中解析四则运算表达式的算法和示例

作者:junjie 时间:2024-04-28 09:41:37 

在编写代码时我们有时候会碰到需要自己解析四则运算表达式的情况,本文简单的介绍使用JavaScript实现对简单四则运算表达式的解析。

一、熟悉概念

中缀表示法(或中缀记法)是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4)。也就是我们最常用的算术表达式,中缀表达式对于人类来说比较容易理解,但是不易于计算机解析。

逆波兰表示法(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。逆波兰表示法容易使用堆栈结构对表达式进行解析并计算,所以,这里我们解析四则元素表达式,是先从中缀表达式,转换为逆波兰表达式。然后再计算值。

二、转换流程

中缀表达式转换为后缀表达式(调度场算法)

1.输入队列弹出一个记号
2.如果记号为数字,添加到输出队列中
3.如果是一个操作符(+-*/)则比较它与输出堆栈中栈顶的操作符,如果优先级小于或等于栈顶的操作符,那么将栈顶的操作符弹出并加入输出队列(循环,直到上述条件不满足),最后将本次的操作符压入堆栈。
4.如果是一个左括号,压入堆栈
5.如果是一个右括号,从栈中不断的弹出操作符,并加入输出队列,知道栈顶的元素为左括号。弹出左括号,不加入输出队列。如果没有发现左括号,说明原来的表达式中括号不对称,有错误。
6.如果输入队列为空,而栈中尚有操作符时,如果栈顶的操作符为左括号,则说明原表达式有不匹配的括号。将栈中的操作符逐个弹出,加入输出队列。
7.完成

javascript中解析四则运算表达式的算法和示例

三、转换代码实现


function isOperator(value){
var operatorString = "+-*/()";
return operatorString.indexOf(value) > -1
}

function getPrioraty(value){
switch(value){
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}

function prioraty(o1, o2){
return getPrioraty(o1) <= getPrioraty(o2);
}

function dal2Rpn(exp){
var inputStack = [];
var outputStack = [];
var outputQueue = [];

for(var i = 0, len = exp.length; i < len; i++){
var cur = exp[i];
if(cur != ' ' ){
inputStack.push(cur);
}
}
console.log('step one');
while(inputStack.length > 0){
var cur = inputStack.shift();
if(isOperator(cur)){
if(cur == '('){
outputStack.push(cur);
}else if(cur == ')'){
var po = outputStack.pop();
while(po != '(' && outputStack.length > 0){
outputQueue.push(po);
po = outputStack.pop();
}
if(po != '('){
throw "error: unmatched ()";
}
}else{
while(prioraty(cur, outputStack[outputStack.length - 1]) && outputStack.length > 0){
outputQueue.push(outputStack.pop());
}
outputStack.push(cur);
}
}else{
outputQueue.push(new Number(cur));
}
}
console.log('step two');
if(outputStack.length > 0){
if(outputStack[outputStack.length - 1] == ')' || outputStack[outputStack.length - 1] == '('){
throw "error: unmatched ()";
}
while(outputStack.length > 0){
outputQueue.push(outputStack.pop());
}
}
console.log('step three');
return outputQueue;

}

console.log(dal2Rpn('1 + 2'));
console.log(dal2Rpn('1 + 2 + 3'));
console.log(dal2Rpn('1 + 2 * 3'));
console.log(dal2Rpn('1 + 2 * 3 - 4 / 5'));
console.log(dal2Rpn('( 1 + 2 )'));

console.log(dal2Rpn('( 1 + 2 ) * ( 3 - 4 ) / 5'));
console.log(dal2Rpn('( 1 + 2 ) * (( 3 - 4 ) / 5)'));

四、逆波兰表达式求值

1.从输入队列中弹出一个记号
2.如果是操作数,加入输出堆栈
3.如果是一个操作符,从输出堆栈中弹出两个操作数并进行计算,并将计算得到的值压入输出堆栈。
4.循环操作,如果输入队列为空,且输出堆栈只有一个数则这个数为结果,否则是出现了多余的操作数。

五、计算代码


function evalRpn(rpnQueue){
var outputStack = [];
while(rpnQueue.length > 0){
var cur = rpnQueue.shift();

if(!isOperator(cur)){
outputStack.push(cur);
}else{
if(outputStack.length < 2){
throw "unvalid stack length";
}
var sec = outputStack.pop();
var fir = outputStack.pop();

outputStack.push(getResult(fir, sec, cur));
}
}

if(outputStack.length != 1){
throw "unvalid expression";
}else{
return outputStack[0];
}
}

六、结语

逆波兰表示法,在初次接触的时候感觉不太习惯,但是熟悉之后,会发现,其实思路特别简单,不像中缀表示法,还有各种优先级啊,还有小括号之类的,逻辑特别麻烦,还是逆波兰表示法比较简洁,完全不用考虑优先级,也没用小括号,中括号还有大括号搅局。

标签:javascript,四则运算表达式
0
投稿

猜你喜欢

  • Golang基础教程之字符串string实例详解

    2024-02-07 22:37:10
  • vue实现点击图片放大效果

    2024-05-21 10:30:28
  • 使用XML技术上传文件的例子

    2008-05-29 11:33:00
  • Python获取指定网段正在使用的IP

    2022-04-22 23:49:27
  • Python3 ID3决策树判断申请贷款是否成功的实现代码

    2021-02-11 15:01:58
  • Oracle字段根据逗号分割查询数据的方法

    2024-01-14 01:34:19
  • SQL Server 2005实现数据库缓存依赖

    2009-05-07 13:20:00
  • Highcharts+NodeJS搭建数据可视化平台示例

    2024-05-02 17:38:38
  • Python生成器常见问题及解决方案

    2023-01-23 19:09:43
  • Scrapy实现模拟登录的示例代码

    2023-07-13 21:53:11
  • ACCESS转SQL Server2000需要注意的问题

    2007-11-18 15:25:00
  • Go语言流程控制之goto语句与无限循环

    2023-08-31 06:43:00
  • Python实现的爬取百度贴吧图片功能完整示例

    2021-06-30 19:22:13
  • MySQL学习(七):Innodb存储引擎索引的实现原理详解

    2024-01-25 05:53:02
  • python之模拟鼠标键盘动作具体实现

    2022-12-23 10:51:29
  • 面包屑设计

    2009-07-07 11:17:00
  • python 命令行传参方法总结

    2021-06-04 20:51:00
  • Python中无限循环需要什么条件

    2023-03-28 09:05:14
  • python list转置和前后反转的例子

    2022-04-26 10:39:55
  • vim中tagbar配置以及打字时隐藏鼠标的方法

    2022-06-23 14:34:49
  • asp之家 网络编程 m.aspxhome.com