简介
调度场算法（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 - + |
网友评论