JavaScript数据结构中栈的应用之表达式求值问题详解
本文实例讲述了JavaScript数据结构中栈的应用之表达式求值问题。分享给大家供大家参考，具体如下：
下面来谈一个比较经典的表达式求值问题，这个问题主要是设计到操作符的优先级。我们通常看到的表达式都是中缀表达式，存在很多优先级差别，而后缀表达式则没有这些优先级问题。下面先看看两种表达式的区别。
中缀表达式：a*b+c*d-e/f
后缀表达式：ab*cd*+ef/-
从中缀表达式转换到后缀表示式是很难实现的，我们这里可以通过栈的思想来实现。下面进行详细的介绍是什么样的思想：
在对一个中缀表示式进行转换的时候，遇到非操作符的字符则直接保存到后缀表示式的存储空间中。
遇到（，则压入栈，只有遇到对应的）才能被弹出。
遇到），就将（之前的操作符全部弹出，并保存到存储空间。
遇到*和/这样优先级高的，就判断栈中的操作符优先级是否低于当前操作符。
如果栈中的遇到的低，则将遇到的继续入栈；如果栈中的高，则将栈中的出栈，遇到的入栈。
最后，当字符串遍历完成，依次弹出操作符，保存到存储空间。
为了方便理解，将上面的例子再次讲解。a*b+c*d-e/f
首先是ab被保存到了存储空间，然后*入栈。现在栈中只有*。
遇到+之后，由于*比+优先级高，所以*出栈，+入栈，这样存储空间变为ab*，栈中变为+。
再时候遇到c，存储空间变为ab*c，栈中还是+。
接下来遇到*和d，由于+比*低，所以*继续入栈，栈中表为了+*，存储空间为ab*cd。
之后遇到-，由于*比-高，所以+*出栈，-入栈，存储空间变为ab*cd*+
……后面不用解释了，悟性再低也应该会了。
下面我们用JavaScript代码来实现下吧。
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title></title>
</head>
<body>
<script type="text/javascript">
function midTOLast(a){
var a_len=a.length;
var myArray=new Array();
b='';
for(var i=0;i<a_len;i++){
switch (a[i]){
case '(':
{
myArray.push(a[i]);
break;
}
case ')'://如果是）则将栈中左括号之前的对象弹出
{
if(myArray.length==0){
return false;
}
temp=myArray.pop();//非空，弹出对象
while(temp!='('){//只要不是左括号，则全部弹出
b+=temp;//并输出到后缀表达式中
if(myArray.length==0){//保证栈为空
break;
}
temp=myArray.pop();
}
break;
}
case '*':
case '/':
{
if(myArray.length==0){//如果栈为空则直接入栈
myArray.push(a[i]);
}else{
temp=myArray[myArray.length-1];
if(temp=='+'||temp=='-'){//如果遇到高的，则遇到的继续入栈
myArray.push(a[i]);//遇到的入栈
}
}
break;
}
case '+':
case '-':
{
if(myArray.length==0){//如果栈为空则直接入栈
myArray.push(a[i]);
}else{
temp=myArray[myArray.length-1];
if(temp=='/'||temp=='*'){//如果遇到低的，则栈中的出栈，遇到的入栈
while(myArray.length!=0){
temp=myArray.pop();//栈中的出栈
b+=temp;//保存到存储空间
}
myArray.push(a[i]);//遇到的入栈
}
}
break;
}
default:
{
b+=a[i];
break;
}
}
}
//最后将栈中剩下的操作符输出
while(myArray.length!=0){
temp=myArray.pop();
b+=temp;
}
return true;
}
var x="a*b+c*d-e/f";
midTOLast(x);
alert(b);//ab*cd*+ef/-
</script>
</body>
</html>
当然，以上程序还存在一点bug，但是思想应该就是这样子的。
下面，我们将讲解如何通过后缀表达式计算出表达式的结果。
那么，我们将中缀表达式转化为后缀表达式后，如何继续计算呢？还是以这个例子为例。
中缀表达式：a*b+c*d-e/f
后缀表达式：ab*cd*+ef/-
基本思路如下：
遍历后缀表达式，遇到非操作符的字符则直接进栈，遇到操作符则出栈两个元素，进行对应操作，然后将得到的结果再次入栈。依次直到遍历完成，此处栈中保存的值就是当前表达式的值。
实现的JavaScript代码如下：
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title></title>
</head>
<body>
<script type="text/javascript">
function getValue(a){
var a_len=a.length,
myArray=new Array();
for(var i=0;i<a_len;i++){
switch (a[i])
{//遇到数值则直接入栈
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
{
myArray.push(a[i]);
break;
}
case '+':
{//遇到操作符则出栈两个元素进行对应操作
temp=myArray.pop()+myArray.pop();
myArray.push(temp);//再将结果入栈
temp=null;
break;
}
case '-':
{
s=myArray.pop();
temp=myArray.pop()-s;
myArray.push(temp);
s=null;temp=null;
break;
}
case '*':
{
temp=myArray.pop()*myArray.pop();
myArray.push(temp);//再将结果入栈
temp=null;
break;
}
case '/':
{
s=myArray.pop();
temp=myArray.pop()/s;
myArray.push(temp);
s=null;temp=null;
break;
}
}
}
return myArray.pop();//算出结果
}
var a="12*34*+36/-";//1*2+3*4-3/6
var b=getValue(a);//13.5
alert(b);
</script>
</body>
</html>
好啦，栈的应用场景还有很多，比如进制的转换，行编辑程序，迷宫求解等。这里就不一一介绍了。
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
相关推荐
-
JavaScript中数据结构与算法(一)：栈
序 数据结构与算法JavaScript这本书算是讲解得比较浅显的,优点就是用javascript语言把常用的数据结构给描述了下,书中很多例子来源于常见的一些面试题目,算是与时俱进,业余看了下就顺便记录下来吧 git代码下载:https://github.com/JsAaron/data_structure.git 栈结构 特殊的列表,栈内的元素只能通过列表的一端访问,栈顶 后入先出(LIFO,last-in-first-out)的数据结构 javascript提供可操作的方法, 入栈 push,
-
使用JavaScript实现链表的数据结构的代码
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer) - 维基百科 上面是维基百科对 链表 的解读.下面我们用 JavaScript 代码对链表的数据结构进行实现 实现Node类表示节点 /** * Node 类用来表示节点 * element 用来保存节点上的数据 * next 用来保存指向下一个节点的链接 */ function Node(element) { this.elemen
-
JavaScript数据结构学习之数组、栈与队列
前言 数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合. 常用的数据结构有: 数组,队列(queue),堆(heap),栈(stack),链表(linked list ),树(tree),图(graph)和散列表(hash) 本文主要介绍的是数组.栈与队列,下面来一起看看详细的介绍吧. 一.数组 数组是平时使用最常用的数据结构,在JavaScript中数组是动态的分配大小,在这里我不会介绍JavaScript里面数组的所有的方法,而是针对数据结构这个方向谈谈所用到的方法
-
JavaScript数据结构与算法之栈与队列
学习起因 曾经有一次在逛V2EX时,碰到这么一个帖子. 数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐? 发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作.感觉到数学知识的匮乏,所以想补一补数学. 看了看帖子,感觉和我很像,因为我的专业是不开高数的,我学的也是前端.也同样感觉到了数学知识匮乏所带来的困顿.同时因为自己的数学思维实在是不怎么好,所以决定努力补习数学与计算机基础知识. 当时也有人说:"前端需要什么数据结构与算法",但是对于这个事情我有自己
-
JavaScript数组实现数据结构中的队列与堆栈
一.队列和堆栈的简单介绍 1.1.队列的基本概念 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 如下图所示: 1.2.堆栈的基本概念 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 如下图所示: 二. 在JavaScript中实现队列和堆栈 在JavaScript中实现队列和数组主要是通过数组,js数组中提供了以下几个方法可以让我们很方便实现队列和堆栈: •shift:从数组中把第一个元素删除,并返回这个元素的值. •unshift: 在数组
-
JavaScript数据结构与算法之栈详解
在上一篇博客介绍了下列表,列表是最简单的一种结构,但是如果要处理一些比较复杂的结构,列表显得太简陋了,所以我们需要某种和列表类似但是更复杂的数据结构---栈.栈是一种高效的数据结构,因为数据只能在栈顶添加或删除,所以这样操作很快,而且容易实现. 一:对栈的操作. 栈是一种特殊的列表,栈内的元素只能通过列表的一端访问,这一端陈为栈顶.比如餐馆里面洗盘子,只能先洗最上面的盘子,盘子洗完后,也只能螺到这一摞盘子的最上面.栈被称为 "后入先出"(LIFO)的数据结构. 由于栈具有后入先出的特点
-
利用JavaScript实现栈的数据结构示例代码
前言 本文主要给大家介绍的是关于JavaScript实现栈的数据结构的相关内容,分享出来供大家参考学习,话不多少,来一起看看详细的介绍: 堆栈(英语:stack),也可直接称栈,在计算机科学中,是一种特殊的串列形式的数据结构,它的特殊之处在于只能允许在链接串列或阵列的一端(称为堆叠顶端指标,英语:top)进行加入数据(push)和输出数据(pop)的运算.另外栈也可以用一维数组或连结串列的形式来完成. 由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First
-
JavaScript数据结构中栈的应用之表达式求值问题详解
本文实例讲述了JavaScript数据结构中栈的应用之表达式求值问题.分享给大家供大家参考,具体如下: 下面来谈一个比较经典的表达式求值问题,这个问题主要是设计到操作符的优先级.我们通常看到的表达式都是中缀表达式,存在很多优先级差别,而后缀表达式则没有这些优先级问题.下面先看看两种表达式的区别. 中缀表达式:a*b+c*d-e/f 后缀表达式:ab*cd*+ef/- 从中缀表达式转换到后缀表示式是很难实现的,我们这里可以通过栈的思想来实现.下面进行详细的介绍是什么样的思想: 在对一个中
-
python四则运算表达式求值示例详解
目录 四则运算表达式求值 思路说明 算法步骤 代码 四则运算表达式求值 思路说明 使用双栈来实现——存放数值的栈 nums 与存放运算符的栈 ops. 算法步骤 对原始表达式字符串 exp 进行预处理, 将其转为一个元素对应一个数值或运算符的列表 explist. 遍历 explist , 每个元素依次压入对应的栈中. 每次压入后, 判断当前两栈顶是否可进行乘除运算.栈顶可进行乘除运算的充要条件是, ops 栈顶为<*> ,</> 之一, 且 nums 中的元素比 ops 中的元素
-
javascript数据结构中栈的应用之符号平衡问题
本文实例讲述了javascript数据结构中栈的应用之符号平衡问题.分享给大家供大家参考,具体如下: 由于栈先进后出的结构,我们可以将其作为有用的工具,下面就介绍一下栈的应用. 首先是符号的平衡问题.有一串字符串,我们需要判断其中固定的字符是否成对出现,比如<> {} [] () 等.当然实现的方法有很多,但是采用栈的实现会相对更加简单. 实现上述算法的JavaScript代码如下 <!DOCTYPE html> <html> <head> <meta
-
C语言中栈和队列实现表达式求值的实例
C语言中栈和队列实现表达式求值的实例 实现代码: #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define STACK_SIZE 20 #define STACK_INCREMENT 10 #define QUEUE_SIZE 20 typedef int Status; typedef char StackElemtype; typedef struct Stack{ StackElemty
-
java 数据结构中栈和队列的实例详解
java 数据结构中栈和队列的实例详解 栈和队列是两种重要的线性数据结构,都是在一个特定的范围的存储单元中的存储数据.与线性表相比,它们的插入和删除操作收到更多的约束和限定,又被称为限定性的线性表结构.栈是先进后出FILO,队列是先进先出FIFO,但是有的数据结构按照一定的条件排队数据的队列,这时候的队列属于特殊队列,不一定按照上面的原则. 实现栈:采用数组和链表两种方法来实现栈 链表方法: package com.cl.content01; /* * 使用链表来实现栈 */ public cl
-
JavaScript数据结构中串的表示与应用实例
本文实例讲述了JavaScript数据结构中串的表示与应用.分享给大家供大家参考,具体如下: 类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列.下面我们以串联接为例,讲解一下这种存储结构时串的操作.JavaScript自带有concat方法,该方法返回字符串值,该值包含了两个或多个提供的字符串的连接. 其实思路很简单,就是将第二个串拼接在第一个串后面,代码如下 <!DOCTYPE html> <html> <head> <meta chars
-
java 数据结构中栈结构应用的两个实例
java 数据结构中栈结构应用的两个实例 1.单词逆序. 要求从控制台读入一串字符,按回车结束输入,同时显示其逆序字符串. 对于颠倒顺序的操作,用栈来解决是很方便的.具体思想是把字符串中的每一个字符按顺序存入栈中,然后再一个一个的从栈中取出.这时就是按照逆序取出的字符串. // reverse.java // stack used to reverse a string // to run this program: C>java ReverseApp import java.io.*; //
-
数据结构课程设计-用栈实现表达式求值的方法详解
1.需求分析设计一个程序,演示用算符优先法对算术表达式求值的过程.利用算符优先关系,实现对算术四则混合运算表达式的求值.(1)输入的形式:表达式,例如2*(3+4) 包含的运算符只能有'+' .'-' .'*' .'/' .'('. ')':(2)输出的形式:运算结果,例如2*(3+4)=14:(3)程序所能达到的功能:对表达式求值并输出 2.系统设计1.栈的抽象数据类型定义:ADT Stack{数据对象:D={ai|ai∈ElemSet,i=1,2,-,n,n≥0}数据关系:R1={<
-
Java栈的运用之中缀表达式求值详解
目录 栈运用题:中缀表达式求值 题目详情 解题思路 实现代码 栈运用题:中缀表达式求值 题目详情 给定一个表达式,其中运算符仅包含 +,-,*,/(加 减 乘 整除),可能包含括号,请你求出表达式的最终值. 注意: 数据保证给定的表达式合法. 题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现. 题目保证表达式中所有数字均为正整数. 题目保证表达式在中间计算过程以及结果中,均不超过 231−1. 题目中的整除是指向 0 取整
-
C++利用链栈实现表达式求值
本文实例为大家分享了C++利用链栈实现表达式求值的具体代码,供大家参考,具体内容如下 #include<iostream.h> typedef int Status; typedef char Cstack; #define OK 1 #define ERROR 0 typedef struct StackNode { Cstack data; struct StackNode *next; }StackNode,*LinkStack; Status InitStack(LinkStack &