内容来自尚硅谷Java数据结构与java算法（Java数据结构与算法）_哔哩哔哩_bilibili

写在前面:本文内容大致和原视频内老师的笔记内容相同，会偶尔插入自己的注释和理解，尽量会完成作业

本次有一个加入括号的作业，但是老师提到了后面会讲，所以当时想了一小会，然后决定继续学习[del]其实就是不会[/del]

5.5栈实现综合计算器(中缀表达式)

使用栈来实现综合计算器

请输入一个表达式

计算式:[7*2*2-5+1-5+3-3]

思路分析(图解):

代码实现

1.     先实现1位数的运算

2.     扩展到多位数的运算

5.6逆波兰计算器

1.      输入一个逆波兰表达式(后缀表达式)，使用栈(Stack)，计算其结果

2.      支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。

3.      思路分析

例如:(3+4)×5-6对应的后缀表达式就是34+5 ×6-，针对后缀表达式求值步骤如下:

Step1.从左至右扫描，将3和4压入堆栈;

Step2.遇到+运算符，因此弹出4和3(4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈;

Step3.将5入栈;

Step4.接下来是*运算符，因此弹出5和7，计算出7×5=35，将35入栈;

Step5.将6入栈;

最后是-运算符，计算出35-6的值，即29，由此得出最终结果

4.      代码完成

5.7中缀表达式转换为后缀表达式

大家看到，后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将中缀表达式转成后缀表达式。

5.7.1具体步骤如下:

1.初始化两个栈:运算符栈s1和储存中间结果的栈s2;

2.从左至右扫描中缀表达式;

3.遇到操作数时，将其压s2;

4.遇到运算符时，比较其与s1栈顶运算符的优先级:

4.1如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈;

4.2否则，若优先级比栈顶运算符的高，也将运算符压入s1;

4.3否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较;

5.遇到括号时:

5.1如果是左括号“(”，则直接压入s1

5.2如果是右括号“)"，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃

6.重复步骤2至5，直到表达式的最右边

7.将s1中剩余的运算符依次弹出并压入s2

8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达书

5.7.2举例说明

将中缀表达式”1+((2+3)*4)-5”转换为后缀表达式的过程如下

此结果为:”1 2 3 + 4 * + 5 -”

5.7.3代码实现中缀表达式转为后缀表达式

思路分析

代码实现：