javascript中解析四则运算表达式的算法和示例
作者:junjie 发布时间:2024-04-28 09:41:37
在编写代码时我们有时候会碰到需要自己解析四则运算表达式的情况,本文简单的介绍使用JavaScript实现对简单四则运算表达式的解析。
一、熟悉概念
中缀表示法(或中缀记法)是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4)。也就是我们最常用的算术表达式,中缀表达式对于人类来说比较容易理解,但是不易于计算机解析。
逆波兰表示法(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。逆波兰表示法容易使用堆栈结构对表达式进行解析并计算,所以,这里我们解析四则元素表达式,是先从中缀表达式,转换为逆波兰表达式。然后再计算值。
二、转换流程
中缀表达式转换为后缀表达式(调度场算法)
1.输入队列弹出一个记号
2.如果记号为数字,添加到输出队列中
3.如果是一个操作符(+-*/)则比较它与输出堆栈中栈顶的操作符,如果优先级小于或等于栈顶的操作符,那么将栈顶的操作符弹出并加入输出队列(循环,直到上述条件不满足),最后将本次的操作符压入堆栈。
4.如果是一个左括号,压入堆栈
5.如果是一个右括号,从栈中不断的弹出操作符,并加入输出队列,知道栈顶的元素为左括号。弹出左括号,不加入输出队列。如果没有发现左括号,说明原来的表达式中括号不对称,有错误。
6.如果输入队列为空,而栈中尚有操作符时,如果栈顶的操作符为左括号,则说明原表达式有不匹配的括号。将栈中的操作符逐个弹出,加入输出队列。
7.完成
三、转换代码实现
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];
}
}
六、结语
逆波兰表示法,在初次接触的时候感觉不太习惯,但是熟悉之后,会发现,其实思路特别简单,不像中缀表示法,还有各种优先级啊,还有小括号之类的,逻辑特别麻烦,还是逆波兰表示法比较简洁,完全不用考虑优先级,也没用小括号,中括号还有大括号搅局。
猜你喜欢
- 什么是PRC&GRPCRPC是远程过程调用(Remote Procedure Call)的缩写形式, RPC 的主要功能目标是让构建
- pandas可以将读取到的表格型数据(文件不一定要是表格)转成DataFrame类型的数据结构,然后我们可以通过操作DataFrame进行数
- 字典求和edge_weights = defaultdict(lambda: defaultdict(float))for idx,node
- 粒子群算法是一种基于鸟类觅食开发出来的优化算法,它是从随机解出发,通过迭代寻找最优解,通过适应度来评价解的品质。PSO算法的搜索性能取决于其
- 在开发中中我们经常会使用到数据库连接池,比如dbcp数据库连接池,本章将讲解java连接dbcp数据库库连接池的简单使用。开发工具myecl
- 简介pygame模块用于变换Surface,Surface变换是一种移动或调整像素大小的操作。所有这些函数都是对一个Surface进行操作,
- 本文实例讲述了python判断一个集合是否包含了另外一个集合中所有项的方法。分享给大家供大家参考。具体如下:>>> L1
- 前言迭代器是 23 种设计模式中最常用的一种(之一),在 Python 中随处可见它的身影,我们经常用到它,但是却不一定意识到它的存在。在关
- 前段时间自学了python,作为新手就想着自己写个东西能练习一下,了解到python编写爬虫脚本非常方便,且最近又学习了MongoDB相关的
- 一、torch.utils.data.DataLoader 简介作用:torch.utils.data.DataLoader 主要是对数据进
- 前言我们在django-rest-framework 自定义swagger 文章中编写了接口, 调通了接口文档. 接口文档可以直接填写参数进
- Python版本 实现了比之前的xxftp更多更完善的功能 1、继续支持多用户 2、继续支持虚拟目录 3、增加支持用户根目录以及映射虚拟目录
- 系统环境centos7python2.7先在操作系统安装expect[root@V71 python]# vi 3s.py#!/usr/bi
- 看代码吧~name = input('Name') height = input('Height(m):')
- 前奏为了能操作数据库, 首先我们要有一个数据库, 所以要首先安装Mysql, 然后创建一个测试数据库python_test用以后面的测试使用
- 一、 前提:有Google账号(具体怎么注册账号这里不详述,大家都懂的,自行百度)在你的Google邮箱中关联好colab(怎样在Googl
- 首先介绍一下什么是桑葚图?桑基图(Sankey diagram),即桑基能量分流图,也叫桑基能量平衡图。它是一种特定类型的流程图,图中延伸的
- numpy.linalg.norm函数的使用1、linalg = linear(线性)+ algebra(代数),norm则表示范数。首先需
- 迭代器跟生成器,与上篇文章讲的装饰器一样,都是属于我的一个老大难问题。通常就是遇到的时候就去搜一下,结果在一大坨各种介绍博客中看了看,回头又
- Google Maps JavaScript. API可以让您在自己的网页上使用Google地图.在使用API之前,您应该先申请一 个API