计算中缀表达式 - 调度场算法

简介

调度场算法（Shunting Yard Algorithm）是由Edsger Wybe Dijkstra引入的用于将中缀表达式转换成后缀表达式的经典算法。后缀表达式也称为逆波兰表达式。

目标

输入一个表达式字符串，计算其结果。表达式中数字包括：整数，小数；运算符包括："+"，"-"，"*"，"/"，"("，")"

调度场算法原理

准备一个队列，用于存放后缀表达式。准备一个栈，用于存放运算符。从左到右遍历中缀表达式，如果是数字直接加入到队列中，即成为后缀表达式的一部分。

如果是运算符，则判断与栈顶运算符的优先级：

优先级>栈顶运算符或者栈顶是左括号，则直接压入栈内；

优先级<=栈顶运算符，则栈顶运算符依次出栈并加入到队列中，并将当前运算符进栈。（这里等号保证了连加这种情况是从左到右进行的）

对于左括号直接压入栈内，对于右括号不停弹出栈内运算符，直到找到左括号。

最后将所有栈内运算符依次出栈，加入到队列中。

举例说明

输入字符串： 3 + 3 * ( 6 - 1 * 2 ) / 4 - 1

输入	动作	输出（后缀表达式）	运算符栈	备注
3	数字加入队列中	3
+	运算符入栈	3	+
3	数字加入队列中	3 3	+
*	运算符入栈	3 3	* +	*优先级高于+
(	运算符入栈	3 3	( * +	( 直接进栈
6	数字加入队列中	3 3 6	( * +
-	运算符入栈	3 3 6	- ( * +	括号优先级高于+ - * /
1	数字加入队列中	3 3 6 1	- ( * +
*	运算符入栈	3 3 6 1	* - ( * +
2	数字加入队列中	3 3 6 1 2	* - ( * +
)	不停出栈，直到(	3 3 6 1 2 * -	* +
/	运算符入栈	3 3 6 1 2 * -	/ * +
4	数字加入队列中	3 3 6 1 2 * - 4	/ * +
-	栈顶出栈两个，并加到队列中	3 3 6 1 2 * - 4 / *	- +
1	数字加入队列中	3 3 6 1 2 * - 4 / * 1	+ +
END	栈依次出栈加入队列	3 3 6 1 2 * - 4 / * 1 - +