栈在表达式求值中的应用

李橙+丁国栋

摘要：栈是限定只能在表的一端进行插入和删除的线性表。根据栈的这种存取特征，栈也被称为后进先出表。生活中的穿衣脱衣、九连环游戏、括号匹配等都是应用栈的这一特点。栈的基本操作包括入栈、出栈、得到栈顶元素、判断栈空、判断栈满等等。在该文中我们将讨论栈在中缀表达式求值、后缀表达式求值以及后缀表达式转换成中缀表达式中的应用。

关键词：栈；数据结构；线性表；表达式求值

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2014）34-8156-02

1 问题描述与分析

中缀表达式：运算符在两个运算数之间的表达式，其中包含运算数、+、-、*、/等各种运算符以及括号。eg.3+9*（1-4）。按照“运算符的优先级”求值。

后缀表达式：运算符在两个运算数之后的表达式，其中包含运算数、+、-、*、/等各种运算符但不包含括号，按照顺序计算法求值。

[中缀表达式＼&后缀表达式＼&A+B*C＼&ABC*+＼&B*（D-C）+A＼&BDC-*A+＼&]

2 核心算法思想

2.1中缀表达式求值的算法思想

需要建立两个辅助数据结构：数据栈用来存放要计算的数据以及产生的结果；符号栈用来存放运算符。

分析：先乘除，后加减，从左到右。

2.2 后缀表达式求值的算法思想

需要建立一个辅助数据结构：数据栈用来存放运算的数据以及产生的结果。

算法：自左向右扫描后缀表达式，直到遇到结束符为止。遇到运算数就进栈，遇到运算符就从数栈中退出两个运算数，进行运算，将运算结果进栈，一直到所有运算全部执行完。

2.3 中缀表达式Mid[]转换为后缀表达式Post[]

3 算法中涉及到的辅助数据结构

4 跟踪实例

4.1中缀表达式求值：Mid=”3*（7-2）#”

4.2 中缀表达式转换成后缀表达式

5 算法具体实现

5.1中缀表达式求值算法

5.2后缀表达式求值算法

5.3后缀表达式转换成中缀表达式的算法

6 结束语

数据结构是计算机专业中非常重要的一门专业基础课，但很多同学反映数据结构的学习存在各种各样的难点，其中比较复杂的是数据结构中存在各种各样的存储结构，它们有着不同的逻辑结构、不同的存储结构、不同的运算操作以及不同的应用。另外和C语言中不同，数据结构中的程序由于要定义各种结构，分配各种存储空间，定义各种初始化操作，数据结构中的程序都比较复杂也比较长，所以在数据结构课程中编写程序要比在C语言中编写程序复杂得多。如果我们能够在各种数据结构的基础上拓展其有趣的应用，我们就能激发学生的学习和编程兴趣。

参考文献：

[1] 谭浩强.C语言程序设计教程[M].北京：高等教育出版社，1991.

[2] 李志刚.数据仓库与数据挖掘的原理及应用[M]. 北京：高等教育出版社，2008.

[3] 张俊妮.数据挖掘与应用[M]. 北京：北京大学出版社，2009.

[4] 严蔚敏.数据结构（C语言版）[M].北京：清华大学出版社，2007.

[5] 李廉治，姜文清，郭福顺.数据结构[M].大连：大连理工大学出版社，1989.

[6] 陈文伟.数据仓库与数据挖掘教程[M]. 北京：清华大学出版社，2009.

[7] 马靖善.C语言程序设计[M]. 北京：清华大学出版社，2005.

[8] 韩家炜.数据挖掘概念与技术[M]. 北京：机械工业出版社，2007.

[9] 晋良颍.数据结构[M]. 北京：人民邮电出版社，2002.

[10] 许卓群，唐世渭.数据结构[M]. 北京：高等教育出版社，1988.

[11] 魏荣.数据结构[M]. 北京：机械工业出版社，1996.endprint

摘要：栈是限定只能在表的一端进行插入和删除的线性表。根据栈的这种存取特征，栈也被称为后进先出表。生活中的穿衣脱衣、九连环游戏、括号匹配等都是应用栈的这一特点。栈的基本操作包括入栈、出栈、得到栈顶元素、判断栈空、判断栈满等等。在该文中我们将讨论栈在中缀表达式求值、后缀表达式求值以及后缀表达式转换成中缀表达式中的应用。

关键词：栈；数据结构；线性表；表达式求值

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2014）34-8156-02

1 问题描述与分析

中缀表达式：运算符在两个运算数之间的表达式，其中包含运算数、+、-、*、/等各种运算符以及括号。eg.3+9*（1-4）。按照“运算符的优先级”求值。

后缀表达式：运算符在两个运算数之后的表达式，其中包含运算数、+、-、*、/等各种运算符但不包含括号，按照顺序计算法求值。

[中缀表达式＼&后缀表达式＼&A+B*C＼&ABC*+＼&B*（D-C）+A＼&BDC-*A+＼&]

2 核心算法思想

2.1中缀表达式求值的算法思想

需要建立两个辅助数据结构：数据栈用来存放要计算的数据以及产生的结果；符号栈用来存放运算符。

分析：先乘除，后加减，从左到右。

2.2 后缀表达式求值的算法思想

需要建立一个辅助数据结构：数据栈用来存放运算的数据以及产生的结果。

算法：自左向右扫描后缀表达式，直到遇到结束符为止。遇到运算数就进栈，遇到运算符就从数栈中退出两个运算数，进行运算，将运算结果进栈，一直到所有运算全部执行完。

2.3 中缀表达式Mid[]转换为后缀表达式Post[]

3 算法中涉及到的辅助数据结构

4 跟踪实例

4.1中缀表达式求值：Mid=”3*（7-2）#”

4.2 中缀表达式转换成后缀表达式

5 算法具体实现

5.1中缀表达式求值算法

5.2后缀表达式求值算法

5.3后缀表达式转换成中缀表达式的算法

6 结束语

数据结构是计算机专业中非常重要的一门专业基础课，但很多同学反映数据结构的学习存在各种各样的难点，其中比较复杂的是数据结构中存在各种各样的存储结构，它们有着不同的逻辑结构、不同的存储结构、不同的运算操作以及不同的应用。另外和C语言中不同，数据结构中的程序由于要定义各种结构，分配各种存储空间，定义各种初始化操作，数据结构中的程序都比较复杂也比较长，所以在数据结构课程中编写程序要比在C语言中编写程序复杂得多。如果我们能够在各种数据结构的基础上拓展其有趣的应用，我们就能激发学生的学习和编程兴趣。

参考文献：

[1] 谭浩强.C语言程序设计教程[M].北京：高等教育出版社，1991.

[2] 李志刚.数据仓库与数据挖掘的原理及应用[M]. 北京：高等教育出版社，2008.

[3] 张俊妮.数据挖掘与应用[M]. 北京：北京大学出版社，2009.

[4] 严蔚敏.数据结构（C语言版）[M].北京：清华大学出版社，2007.

[5] 李廉治，姜文清，郭福顺.数据结构[M].大连：大连理工大学出版社，1989.

[6] 陈文伟.数据仓库与数据挖掘教程[M]. 北京：清华大学出版社，2009.

[7] 马靖善.C语言程序设计[M]. 北京：清华大学出版社，2005.

[8] 韩家炜.数据挖掘概念与技术[M]. 北京：机械工业出版社，2007.

[9] 晋良颍.数据结构[M]. 北京：人民邮电出版社，2002.

[10] 许卓群，唐世渭.数据结构[M]. 北京：高等教育出版社，1988.

[11] 魏荣.数据结构[M]. 北京：机械工业出版社，1996.endprint

摘要：栈是限定只能在表的一端进行插入和删除的线性表。根据栈的这种存取特征，栈也被称为后进先出表。生活中的穿衣脱衣、九连环游戏、括号匹配等都是应用栈的这一特点。栈的基本操作包括入栈、出栈、得到栈顶元素、判断栈空、判断栈满等等。在该文中我们将讨论栈在中缀表达式求值、后缀表达式求值以及后缀表达式转换成中缀表达式中的应用。

关键词：栈；数据结构；线性表；表达式求值

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2014）34-8156-02

1 问题描述与分析

中缀表达式：运算符在两个运算数之间的表达式，其中包含运算数、+、-、*、/等各种运算符以及括号。eg.3+9*（1-4）。按照“运算符的优先级”求值。

后缀表达式：运算符在两个运算数之后的表达式，其中包含运算数、+、-、*、/等各种运算符但不包含括号，按照顺序计算法求值。

[中缀表达式＼&后缀表达式＼&A+B*C＼&ABC*+＼&B*（D-C）+A＼&BDC-*A+＼&]

2 核心算法思想

2.1中缀表达式求值的算法思想

需要建立两个辅助数据结构：数据栈用来存放要计算的数据以及产生的结果；符号栈用来存放运算符。

分析：先乘除，后加减，从左到右。

2.2 后缀表达式求值的算法思想

需要建立一个辅助数据结构：数据栈用来存放运算的数据以及产生的结果。

算法：自左向右扫描后缀表达式，直到遇到结束符为止。遇到运算数就进栈，遇到运算符就从数栈中退出两个运算数，进行运算，将运算结果进栈，一直到所有运算全部执行完。

2.3 中缀表达式Mid[]转换为后缀表达式Post[]

3 算法中涉及到的辅助数据结构

4 跟踪实例

4.1中缀表达式求值：Mid=”3*（7-2）#”

4.2 中缀表达式转换成后缀表达式

5 算法具体实现

5.1中缀表达式求值算法

5.2后缀表达式求值算法

5.3后缀表达式转换成中缀表达式的算法

6 结束语

数据结构是计算机专业中非常重要的一门专业基础课，但很多同学反映数据结构的学习存在各种各样的难点，其中比较复杂的是数据结构中存在各种各样的存储结构，它们有着不同的逻辑结构、不同的存储结构、不同的运算操作以及不同的应用。另外和C语言中不同，数据结构中的程序由于要定义各种结构，分配各种存储空间，定义各种初始化操作，数据结构中的程序都比较复杂也比较长，所以在数据结构课程中编写程序要比在C语言中编写程序复杂得多。如果我们能够在各种数据结构的基础上拓展其有趣的应用，我们就能激发学生的学习和编程兴趣。

参考文献：

[1] 谭浩强.C语言程序设计教程[M].北京：高等教育出版社，1991.

[2] 李志刚.数据仓库与数据挖掘的原理及应用[M]. 北京：高等教育出版社，2008.

[3] 张俊妮.数据挖掘与应用[M]. 北京：北京大学出版社，2009.

[4] 严蔚敏.数据结构（C语言版）[M].北京：清华大学出版社，2007.

[5] 李廉治，姜文清，郭福顺.数据结构[M].大连：大连理工大学出版社，1989.

[6] 陈文伟.数据仓库与数据挖掘教程[M]. 北京：清华大学出版社，2009.

[7] 马靖善.C语言程序设计[M]. 北京：清华大学出版社，2005.

[8] 韩家炜.数据挖掘概念与技术[M]. 北京：机械工业出版社，2007.

[9] 晋良颍.数据结构[M]. 北京：人民邮电出版社，2002.

[10] 许卓群，唐世渭.数据结构[M]. 北京：高等教育出版社，1988.

[11] 魏荣.数据结构[M]. 北京：机械工业出版社，1996.endprint