当前位置：
> > 查看文章
栈和队列6|中缀表达式转换为后缀表达式 – 数据结构和算法28
接下来是数字3，输出，紧跟着是“)”，此时，我们需要去匹配栈里的“(”，然后再匹配前将栈顶数据依次出栈（这就好比括号里优先执行的道理）：
中缀表达式转换为后缀表达式
紧接着是符号“*”，直接入栈：
中缀表达式转换为后缀表达式
遇到数字4，输出，之后是符号“+”，此时栈顶元素是符号“*”，按照先乘除后加减原理，此时栈顶的乘号优先级比即将入栈的加好要大，所以出栈。
栈中第二个元素是加好，按理来说大家平起平坐，但是按照先到先来后到吃屎的原则，栈里的加好呆得太久了，也要出栈透透气。（同理如果栈里还有其他操作符，也是出栈）
最后把刚刚吃屎的那个加好入栈，操作如下图：
中缀表达式转换为后缀表达式
紧接着数字10，输出，最后是符号“/”，进栈：
中缀表达式转换为后缀表达式
最后一个数字5，输出，所有的输入处理完毕，但是栈中仍然有数据，所以将栈中符号依次出栈。
有些东西看上去很难，但事实上做起来会更加的麻烦，就像这道题，小甲鱼要求大家务必经过自己的思考，再跟着小甲鱼来打代码，一定会有更大的收获！
总结规则：从左到右遍历中缀表达式的每个数字和符号，若是数字则直接输出，若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号，则栈顶元素依次出栈并输出，直到遇到左括号或栈空才将吃屎的那个符号入栈。
分页阅读：
小甲鱼在干啥
如果您觉得小甲鱼的视频能够给您带来知识和快乐，您可以选择赞助我们，让我们可以持续为您推出更多精彩的原创编程教学^_^
手机用户打开支付宝钱包，扫描下方支付宝二维码即可：
电脑用户点击下方按钮即可跳转至支付宝转账页面：
感谢您对我们发展的支持和认可！
更多新鲜事儿
加载中……1、堆栈-Stack
& & & 堆栈（也简称作栈）是一种特殊的线性表，堆栈的数据元素以及数据元素间的逻辑关系和线性表完全相同，其差别是线性表允许在任意位置进行插入和删除操作，而堆栈只允许在固定一端进行插入和删除操作。
堆栈中允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。堆栈的插入和删除操作通常称为进栈或入栈，堆栈的删除操作通常称为出栈或退栈。
Java中已经出了Stack的具体实现类
& & &堆栈的数据集合可以表示为a0,a1,…,an-1，每个数据元素的数据类型可以是任意的类类型。
　（1）入栈push(obj)：把数据元素obj插入堆栈。
　（2）出栈pop()：出栈, 删除的数据元素由函数返回。
　（3）取栈顶数据元素getTop()：取堆栈当前栈顶的数据元素并由函数返回。
& （4）非空否notEmpty()：若堆栈非空则函数返回true，否则函数返回false。
堆栈是各种软件系统中应用最广泛的数据结构之一。括号匹配和表达式计算是编译软件中的基本问题，其软件设计中都需要使用堆栈。
首先来看应用之一：
中缀表达式转为后缀表达式
1、前缀表达式(Prefix Notation)是指将运算符写在前面操作数写在后面的不包含括号的表达式，而且为了纪念其发明者波兰数学家Jan Lukasiewicz所以前缀表达式也 & & 叫做“波兰表达式”。比如- 1 + 2 3
2、后缀表达式(Postfix Notation)与之相反，是指运算符写在操作数后面的不含括号的算术表达式，也叫做逆波兰表达式。比如1 2 3 + -
& & 不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：2 1 + 3 *
3、中缀表达式(Infix Notation)就是常用的将操作符放在操作数中间的算术表达式。前缀表达式和后缀表达式相对于中缀表达式最大的不同就是去掉了表示运算优先级 & & & 的括号，比如1-2+3
& & & 在中缀表达式的情况下求值，既要考虑括号，优先级，还要考虑操作出现的先后顺序。但是，作为计算机，其计算过程就显的比较复杂，对于一个中缀表达式，需要不停地对表达式进行多次遍历，来查找相应的计算的信息。这样从算法复杂度上来说，是不可取的。前缀表达式和后缀表达式相对于人们常用的中缀表达式最大的不同就在于表达式中的运算符是按照一定的顺序出现（接下来会具体讲解），所以求值过程中并不需要在表达式中使用括号来指定运算顺序，也不需要在计算过程中其中考虑运算符号的优先级。在采用辅助数据结构的情况下，只需要对表达式进行一次遍历即可计算出结果，大大降低了算法复杂度，也更加符合传统计算机的工作方式。
// 采用中缀表达式的算法分析
将中缀表达式转换为后缀表达式：eg:
(1)当读到数字直接送至输出队列中；
(2)当读到运算符t时：
&&& a.将栈中所有优先级高于或等于t的运算符弹出，送到输出队列中；
& 这句话不好理解，可以说成这样，从栈顶开始，依次弹出比当前处理的运算符优先级高的运算符，直到一个比它优先级低的或者遇到了一个左括号就停止。
&&& b.t进栈；
（3）读到左括号时总是将它压入栈中；
（4）读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列后，再丢弃左括号；
（5）中缀表达式全部读完后，若栈中仍有运算符，将其送到输出队列中。
中缀表达式：3+(2-5)*6/3 转换为后缀表达式的过程：
后缀表达式&&&&&&&&&&&&& 栈
3&&&&&&&&&&&&&&&&&&&&&&& +
3&&&&&&&&&&&&&&&&&&&&&&& +(
32&&&&&&&&&&&&&&&&&&&&&& +(
32&&&&&&&&&&&&&&&&&&&&&& +(-
325&&&&&&&&&&&&&&&&&&&&& +(-
325-&&&&&&&&&&&&&&&&&&&& +
325-&&&&&&&&&&&&&&&&&&&& +*
325-6&&&&&&&&&&&&&&&&&&& +*
325-6*&&&&&&&&&&&&&&&&&& +/
325-6*3&&&&&&&&&&&&&&&&& +/
最终后缀表达式为：325-6*3/+
运用后缀表达式进行计算：
&(1)建立一个栈S；
&(2)从左到右读后缀表达式，读到数字就将它转换为数值压入栈S中，读到运算符则从栈中依次弹出两个数分别到Y和X，然后以“X 运算符 Y”的形式计算机出结果，再压加栈S中；
&(3)如果后缀表达式未读完，就重复上面过程，最后输出栈顶的数值则为结束。
3+(2-5)*6/3=-3 ,其后缀表达式为：325-6*3/+
运算过程如下：
栈&&&&&&&&&&&& 运算
3 2 5&&&&&&&&&&&&&&&&&&&&&&&&& 325入栈
3&&&&&&&&&&&&&& 2-5=-3
3 -3&&&&&&&&&&&&&&&&&&&&&&&&&& 运算结果进栈
3&&&&&&&&&&&&&& -3*6=-18
3 -18 3&&&&&&&& -18/3=-6&&&&&
3 -6&&&&&&&&&&& 3+(-6)=-3&
//------------------------------------------------------
//直接分析：代码解析都给在了注释里面
1 import java.util.S
2 import java.util.regex.P
* 将中缀表达式字符串转换为后缀表达式
7 public class StringToArithmetic {
// 默认构造
public StringToArithmetic() {
// 将中缀表达式字符串计算得到结果
public static double stringToArithmetic(String string) {
return suffixToArithmetic(infixToSuffix(string));
// 将中缀表达式转换为后缀表达式
public static String infixToSuffix(String exp) {
// 创建操作符堆栈
Stack&Character& s = new Stack&Character&();
// 要输出的后缀表达式字符串
String suffix = "";
int length = exp.length(); // 输入的中缀表达式的长度
for (int i = 0; i & i++) {
char// 临时字符变量
// 获取该中缀表达式的每一个字符并进行判断
char ch = exp.charAt(i);
switch (ch) {
// 忽略空格
// 如果是左括号直接压入堆栈
s.push(ch);
// 碰到'+' '-'，将栈中的所有运算符全部弹出去，直至碰到左括号为止，输出到队列中去
while (s.size() != 0) {
temp = s.pop();
if (temp == '(') {
// 重新将左括号放回堆栈，终止循环
s.push('(');
// 没有进入循环说明是当前为第一次进入或者其他前面运算都有括号等情况导致栈已经为空,此时需要将符号进栈
s.push(ch);
// 如果是乘号或者除号，则弹出所有序列，直到碰到加好、减号、左括号为止，最后将该操作符压入堆栈
while (s.size() != 0) {
temp = s.pop();
// 只有比当前优先级高的或者相等的才会弹出到输出队列，遇到加减左括号，直接停止当前循环
if (temp == '+' || temp == '-' || temp == '(') {
s.push(temp);
// 没有进入循环说明是当前为第一次进入或者其他前面运算都有括号等情况导致栈已经为空,此时需要将符号进栈
s.push(ch);
// 如果碰到的是右括号，则距离栈顶的第一个左括号上面的所有运算符弹出栈并抛弃左括号
// 这里假设一定会遇到左括号了，此为自己改进版，已经验证可以过
// while ((temp = s.pop()) != '(') {
// suffix +=
while (!s.isEmpty()) {
temp = s.pop();
if (temp == '(') {
// 默认情况，如果读取到的是数字，则直接送至输出序列
// 如果堆栈不为空，则把剩余运算符一次弹出，送至输出序列
while (s.size() != 0) {
suffix += s.pop();
<span style="color: #0
<span style="color: #1
// 将后缀表达式的进行计算得到运算结果 eg:325-6*3/+
<span style="color: #2
public static double suffixToArithmetic(String exp) {
<span style="color: #3
// 使用正则表达式匹配数字
<span style="color: #4
Pattern pattern = pile("\\d+||(\\d+\\.\\d+)");
<span style="color: #5
// 将后缀表达式分割成字符串数组,此处直接使用空白也可以对字符串进行分割！！
<span style="color: #6
String[] strings = exp.split("");
<span style="color: #7
Stack&Double& stack = new Stack&Double&();
<span style="color: #8
for (int i = 0; i & strings. i++) {
<span style="color: #9
// 这里最好是进行判断彻底消除空格，在该数组的第一位为一个隐形的空格，这里一定要注意在使用exp.split("")剔除空白""
<span style="color: #0
// 由于使用的是""截取导致在数组第一位上面的值为空白
<span style="color: #1
if (strings[i].equals("")) {
<span style="color: #2
<span style="color: #3
<span style="color: #4
// 如果遇到了数字则直接进栈
<span style="color: #5
if (pattern.matcher(strings[i]).matches()) {
<span style="color: #6
stack.push(Double.parseDouble(strings[i]));
<span style="color: #7
<span style="color: #8
// 如果是运算符，则弹出栈顶的两个数进行计算
<span style="color: #9
<span style="color: #0
// ！！！这里需要注意，先弹出的那个数其实是第二个计算数值，这里记作y！
<span style="color: #1
// 自己书写的时候出错
<span style="color: #2
double y = stack.pop();
<span style="color: #3
double x = stack.pop();
<span style="color: #4
// 将运算结果重新压栈
<span style="color: #5
stack.push(calculate(x, y, strings[i]));
<span style="color: #6
<span style="color: #7
<span style="color: #8
// 弹出栈顶元素就是最终结果
<span style="color: #9
return stack.pop();
<span style="color: #0
<span style="color: #1
<span style="color: #2
private static Double calculate(double x, double y, String string) {
<span style="color: #3
// TODO Auto-generated method stub
<span style="color: #4
// 其实使用case逻辑也可以
<span style="color: #5
if (string.trim().equals("+")) {
<span style="color: #6
return x +
<span style="color: #7
<span style="color: #8
if (string.trim().equals("-")) {
<span style="color: #9
return x -
<span style="color: #0
<span style="color: #1
if (string.trim().equals("*")) {
<span style="color: #2
return x *
<span style="color: #3
<span style="color: #4
if (string.trim().equals("/")) {
<span style="color: #5
return x /
<span style="color: #6
<span style="color: #7
return (double) 0;
<span style="color: #8
<span style="color: #9
<span style="color: #0 }
1 import java.io.IOE
2 import java.util.S
* 使用jdk自带stack进行模拟，
* 中缀表达式转为后缀表达式
8 public class Test {
public static void main(String[] args) throws Exception {
<span style="color: #
// Stack&Character& s = new Stack&Character&();
<span style="color: #
<span style="color: #
<span style="color: #
// // 键盘录入一行数据，#号结束录入
<span style="color: #
// // 然后压栈
<span style="color: #
// while ((ch = (char) (System.in.read())) != '#') {
<span style="color: #
// s.push(ch);
<span style="color: #
<span style="color: #
<span style="color: #
// // 弹出堆栈
<span style="color: #
// while (!s.isEmpty()) {
<span style="color: #
// System.out.println(s.pop());
<span style="color: #
<span style="color: #
<span style="color: #
String str = "3+(2-5)*6/3"; // 后缀表达式为： 325-6*3/+
<span style="color: #
String str2 = "3+2-5";
<span style="color: #
<span style="color: #
System.out.println(StringToArithmetic.infixToSuffix(str2));
<span style="color: #
System.out.println(StringToArithmetic.stringToArithmetic(str2));
<span style="color: #
<span style="color: #
// String[] arr = StringToArithmetic.infixToSuffix(str).split("");
<span style="color: #
// for (int i = 0; i & arr. i++) {
<span style="color: #
// if (arr[i].equals("")) {
<span style="color: #
// System.out.println(arr[i]);
<span style="color: #
// System.out.println("我靠
<span style="color: #
<span style="color: #
<span style="color: #
<span style="color: #
// System.out.println(arr[0]);
<span style="color: #
<span style="color: # }
阅读(...) 评论()对于一个给定的后缀表达式，（假设它是合法的）
注意：次算法是基于基本操作符是2元操作符且操作数为一位正整数！
其求&#20540;的基本思想是：对于给定的表达式进行遍历，如果遇到的是操作数就将其压入栈；如果遇到的是操作符，将栈顶的两个元素弹出,假设栈顶两个元素依次为a,b（a在上b在下），将次操作符应用于这两个栈顶元素，比如b-a（注意b在左a在右）然后将计算结果压入栈（用来充当下一个操作符的操作数）；
&最后输出栈顶元素即为结果（其实如果表达式合法最终栈里面一定会只有一个元素）
&#include &stdio.h& //后缀表达式求值
#include &iostream&
#include &cstring&
#include &stack&
#include &ctype.h&
#include &algorithm&
int main()
stack &int&
while(scanf(&%c&,&c)!=EOF)
if(c==&#39;#&#39;)
if(isdigit(c))
s.push(c-&#39;0&#39;);
int a=s.top();
int b=s.top();
case &#39;+&#39;:s.push(b+a);
case &#39;-&#39;:s.push(b-a);
case &#39;*&#39;:s.push(b*a);
case &#39;/&#39;:s.push(b/a);
cout&&s.top()&&
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：330336次
积分：7875
积分：7875
排名：第2619名
原创：423篇
评论：49条
(2)(42)(2)(1)(3)(5)(31)(45)(63)(49)(52)(70)(37)(26)数据结构实验――中缀表达式向后缀表达式的转化(包括四则运算和幂运算)――详细注释_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
数据结构实验――中缀表达式向后缀表达式的转化(包括四则运算和幂运算)――详细注释
&&中缀向后缀的转换,增加了很多详细注释,适合初学链表的同学哦O(∩_∩)O~
你可能喜欢