《数据结构》：中缀表达式合法性判断_Amentos的博客-CSDN博客

目录

一、基本概念

二、中缀表达式转后缀表达式

   例       中缀表达式  2*(3+5)+7/1-4  转换为后缀表达式

三、后缀表达式的计算

   例       后缀表达式  2 3 5 + * 7 1 / + 4 -  的计算

四、算法实现

五、算法改进

1、中缀表达式：

        操作符以中缀形式位于运算数中间（如：3+2），是我们日常通用的算术和逻辑公式表示方法。

2、后缀表达式：

        又称逆波兰式（Reverse Polish Notation - RPN），操作符以后缀形式位于两个运算数后（如：3+2的后缀表达形式就是3 2 +）。

3、前缀表达式：

        又称波兰式（Polish Notation），操作符以前缀形式位于两个运算数前（如：3+2的前缀表达形式就是+ 3 2）。

中缀表达式往往需要使用括号将操作符和对应的操作数括起来，用于指示运算的次序

e.g：5*(2+1) 虽然 * 的优先级高于 +  ，但括号的存在表示应优先执行括号内的 + 运算。

中缀表达式适合于人类的思维结构和运算习惯，但并不适用于计算机

尤其是包含括号的中缀表达式，对计算机而言是非常复杂的结构。

适用于计算机的后缀表达式

与中缀表达式不同，后缀表达式不需要使用括号来标识操作符的优先级。

后缀表达式的计算按 操作符 从左到右出现的顺序依次执行(不考虑运算符之间的优先级)，对于计算机而言是比较简单的结构。

从左至右依次遍历中缀表达式各个字符（需要准备一个字符栈存储操作符和括号）

1、字符为 运算数 ：

直接送入后缀表达式（注：需要先分析出完整的运算数）。

2、字符为 左括号 ：

直接入栈（注：左括号入栈后优先级降至最低）。

3、字符为 右括号 ：

直接出栈，并将出栈字符依次送入后缀表达式，直到栈顶字符为左括号（左括号也要出栈，但不送入后缀表达式）。

总结：只要满足 栈顶为左括号 即可进行最后一次出栈。

4、字符为 操作符 ：

若栈空，直接入栈。

若栈非空，判断栈顶操作符，若栈顶操作符优先级低于该操作符，该操作符入栈；否则一直出栈，并将出栈字符依次送入后缀表达式，直到栈空或栈顶操作符优先级低于该操作符，该操作符再入栈。

总结：只要满足 栈空 或者 优先级高于栈顶操作符 即可停止出栈，并将该操作符入栈。

5、重复以上步骤直至遍历完成中缀表达式，接着判断字符栈是否为空，非空则直接出栈，并将出栈字符依次送入后缀表达式。

注：中缀表达式遍历完成，栈中可能还有字符未输出，故需要判断栈空。

从左至右依次遍历中缀表达式各个字符：

第一个字符为运算数，直接输出：

第二个字符为操作符，满足 栈空/优先级高于栈顶操作符 条件，该操作符入栈：

第三个字符为左括号，直接入栈（入栈后优先级降至最低）：

第四个字符为运算数，直接输出：

第五个字符为操作符，满足 栈空/优先级高于栈顶操作符 条件，该操作符入栈：

第六个字符为运算数，直接输出：

第七个字符为右括号，直接出栈并输出，直到栈顶为左括号时进行最后一次出栈(不输出)：

第八个字符为操作符，不满足 栈空/优先级高于栈顶操作符 条件，出栈直至满足条件

第九个字符为运算数，直接输出：

第十个字符为操作符，满足 栈空/优先级高于栈顶操作符 条件，该操作符入栈：

第十一个字符为运算数，直接输出：

第十二个字符为操作符，不满足 栈空/优先级高于栈顶操作符 条件，出栈直至满足条件：

第十三个字符为运算数，直接输出：

中缀表达式遍历完成，判断字符栈中是否还有操作符，如有则出栈并输出：

转换完成：

从左至右依次遍历后缀表达式各个字符（需要准备一个运算数栈存储运算数和操作结果）

1、字符为 运算数 ：

直接入栈（注：需要先分析出完整的运算数并将其转换为对应的数据类型）

2、字符为 操作符 ：

连续出栈两次，使用出栈的两个数据进行相应计算，并将计算结果入栈

e.g：第一个出栈的运算数为 a ，第二个出栈的运算数为 b ，此时的操作符为 - ，则计算 b-a  （注：a和b顺序不能反），并将结果入栈。

3、重复以上步骤直至遍历完成后缀表达式，最后栈中的数据就是中缀表达式的计算结果。

从左至右依次遍历后缀表达式各个字符：

第一个字符为运算数，直接入栈：

第二个字符为运算数，直接入栈：

第三个字符为运算数，直接入栈：

第四个字符为操作符，直接出栈两次：

继续出栈：

执行： 第二次出栈运算数    操作符    第一次出栈运算数 

即：3 + 5

结果：8

将计算结果入栈：

第五个字符为操作符，直接出栈两次：

执行： 第二次出栈运算数    操作符    第一次出栈运算数 

即：2 * 8

结果：16

将计算结果入栈：

第六个字符为运算数，直接入栈：

第七个字符为运算数，直接入栈：

第八个字符为操作符，直接出栈两次：

执行： 第二次出栈运算数    操作符    第一次出栈运算数 

即：7 / 1

结果：7

将计算结果入栈：

第九个字符为操作符，直接出栈两次：

执行： 第二次出栈运算数    操作符    第一次出栈运算数 

即：16 + 7

结果：23

 将计算结果入栈：

第十个字符为运算数，直接入栈：

第十一个字符为操作符，直接出栈两次：

执行： 第二次出栈运算数    操作符    第一次出栈运算数 

即：23 - 4

结果：19

将计算结果入栈：

后缀表达式遍历完成，栈中数据即为最终计算结果：

程序代码：