调度场算法

调度场算法（Shunting Yard Algorithm）是一个用于将中缀表达式转换为后缀表达式的经典算法，由艾兹格·迪杰斯特拉引入，因其操作类似于火车编组场而得名。

簡例

 

算法示意图，使用了3个空间。输入用符号代替，如果输入是一个数字则直接进输出队列，即图中 b),d),f),h)。如果输入是运算符，则压入操作符堆栈，即图中 c),e)，但是，如果输入运算符的优先级低于或等于运算符栈顶的操作符优先级，则栈内元素进入输出队列，输入操作符压入运算符堆栈，即图中 g)。 最后，运算符堆栈内元素入输出队列，算法结束。

输入：3+4

1. 将3入输出队列（每当输入一个数字时，直接进入输出队列）
2. 将+号压入运算堆栈
3. 将4入输出队列
4. 输入结束，将操作符堆栈中剩余操作符入输出队列
5. 在本情况下只有+号
6. 输出 3 4 +

通过这个例子可以看出两条规则：

• 当读入一个数字时直接入输出队列
• 当输入结束后，运算符队列中所有操作符入输出队列

详细的算法

• 当还有记号可以读取时：

• 读取一个记号。
• 如果这个记号表示一个数字，那么将其添加到输出队列中。
• 如果这个记号表示一个函数，那么将其压入栈当中。
• 如果这个记号表示一个函数参数的分隔符（例如，一个半角逗号 , ）：

• 从栈当中不断地弹出操作符并且放入输出队列中去，直到栈顶部的元素为一个左括号为止。如果一直没有遇到左括号，那么要么是分隔符放错了位置，要么是括号不匹配。

• 如果这个记号表示一个操作符，记做o₁，那么：

• 只要存在另一个记为o₂的操作符位于栈的顶端，并且

如果o₁是左结合性的并且它的运算符优先级要小于或者等于o₂的优先级，或者

如果o₁是右结合性的并且它的运算符优先级比o₂的要低，那么

将o₂从栈的顶端弹出并且放入输出队列中（循环直至以上条件不满足为止）；

• 然后，将o₁压入栈的顶端。

• 如果这个记号是一个左括号，那么就将其压入栈当中。
• 如果这个记号是一个右括号，那么：

• 从栈当中不断地弹出操作符并且放入输出队列中，直到栈顶部的元素为左括号为止。
• 将左括号从栈的顶端弹出，但并不放入输出队列中去。
• 如果此时位于栈顶端的记号表示一个函数，那么将其弹出并放入输出队列中去。
• 如果在找到一个左括号之前栈就已经弹出了所有元素，那么就表示在表达式中存在不匹配的括号。

• 当再没有记号可以读取时：

• 如果此时在栈当中还有操作符：

• 如果此时位于栈顶端的操作符是一个括号，那么就表示在表达式中存在不匹配的括号。
• 将操作符逐个弹出并放入输出队列中。

• 退出算法。

更详细的例子

• 中綴表示法 及 結果：${\displaystyle {{3}+{{{4}\times {2}}\div {{\left({{1}-{5}}\right)}^{{2}^{3}}}}}=3.0001220703125}$ 

  逆波兰表示法：3 4 2 * 1 5 - 2 3 ^ ^ / +

输入: 3 + 4 * 2 / ( 1 − 5 ) ^ 2 ^ 3

输入	动作	输出 (逆波兰表示法)	运算符堆栈	提示
3	将符号加入输出队列	3
+	将符号压入操作符堆栈	3	+
4	将符号加入输出队列	3 4	+
*	将符号压入操作符堆栈	3 4	* +	*号的优先级高于+号
2	将符号加入输出队列	3 4 2	* +
/	将堆栈中元素弹出，加入输出队列	3 4 2 *	+	/号和*号优先级相同
	将符号压入操作符堆栈	3 4 2 *	/ +	/号的优先级高于+号
(	将符号压入操作符堆栈	3 4 2 *	( / +
1	将符号加入输出队列	3 4 2 * 1	( / +
−	将符号压入操作符堆栈	3 4 2 * 1	− ( / +
5	将符号加入输出队列	3 4 2 * 1 5	− ( / +
)	将堆栈中元素弹出，加入输出队列	3 4 2 * 1 5 −	( / +	循环直到找到(号
	将堆栈元素弹出	3 4 2 * 1 5 −	/ +	括号匹配结束
^	将符号压入操作符堆栈	3 4 2 * 1 5 −	^ / +	^号的优先级高于/号
2	将符号加入输出队列	3 4 2 * 1 5 − 2	^ / +
^	将符号压入操作符堆栈	3 4 2 * 1 5 − 2	^ ^ / +	^号为从右至左求值
3	将符号加入输出队列	3 4 2 * 1 5 − 2 3	^ ^ / +
END	将栈中所有数据加入输出队列	3 4 2 * 1 5 − 2 3 ^ ^ / +

C++程序实现

#include <cstring> #include <cstdio> #define op_left_assoc(c) (c == '+' || c == '-' || c == '/' || c == '*' || c == '%') #define is_operator(c) (c == '+' || c == '-' || c == '/' || c == '*' || c == '!' || c == '%' || c == '=') #define is_function(c) (c >= 'A' && c <= 'Z') #define is_ident(c) ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z')) // 操作符 // 优先级 符号 运算顺序 // 1 ! 从右至左 // 2 * / % 从左至右 // 3 + - 从左至右 // 4 = 从右至左 int op_preced(const char c) {  switch (c)   {  case '!':  return 4;  case '*': case '/': case '%':  return 3;  case '+': case '-':  return 2;  case '=':  return 1;  }  //若输入不是运算符  return 0; } unsigned int op_arg_count(const char c) {  switch (c)  {  //运算符  case '*': case '/': case '%': case '+': case '-': case '=':  return 2;  //阶乘  case '!':  return 1;  //不是运算符  default:  return c - 'A';  }  return 0; } bool shunting_yard(const char* input, char* output) {  const char* strpos = input, * strend = input + strlen(input);  char c, stack[32], sc, * outpos = output;  unsigned int sl = 0;  while (strpos < strend)  {  c = *strpos;  if (c != ' ')  {   // 扫描到左括号直接入栈  if (c == '(')  {  stack[sl] = c;  ++sl;  }  // 如果输入为数字，则直接入输出队列  else if (is_ident(c))  {  *outpos = c;  ++outpos;  }  // 如果输入为函数记号，则压入堆栈  else if (is_function(c))  {  stack[sl] = c;  ++sl;  }  // 如果输入为函数分割符（如:逗号）  else if (c == ',')  {  bool pe = false;  while (sl > 0)  {  sc = stack[sl - 1];  //扫描到左括号  //跳出输出循环，此时左括号作为函数边界判定，所以不出栈  if (sc == '(')  {  pe = true;  break;  }  else {  // 栈顶元素不是左括号  // 将栈顶元素依次出栈并放入输出队列  *outpos = sc;  ++outpos;  sl--;  }  }  // 如果没有遇到左括号，则有可能是符号放错或者不匹配  if (!pe)  {  printf("Error: separator or parentheses mismatched\n");  return false;  }  }  // 如果输入符号为运算符，然后:  else if (is_operator(c))  {  while (sl > 0)  {  sc = stack[sl - 1];  // sc为其栈顶元素  // 如果c是左结合性的且它的优先级小于等于栈顶运算符sc的优先级  // 或者c是右结合性且它的优先级小于栈顶运算符sc的优先级  // 将栈顶元素sc出栈，否则sc进栈  if (is_operator(sc) && ((op_left_assoc(c) && (op_preced(c) <= op_preced(sc))) ||   (!op_left_assoc(c) && (op_preced(c) < op_preced(sc)))))   {  *outpos = sc;  ++outpos;  sl--;  }  else  {  break;  }  }  //c的优先级大于或大于等于结合性的要求，则将其入栈  stack[sl] = c;  ++sl;  }  // 扫描到右括号  else if (c == ')')  {  bool pe = false;  // 从栈顶向下扫描左括号，将扫描到左括号之前的栈顶运算符出栈并放入输出队列  while (sl > 0)  {  sc = stack[sl - 1];  if (sc == '(')  {  pe = true;  break;  }  else  {  *outpos = sc;  ++outpos;  sl--;  }  }  // 如果没有扫描到左括号，则有可能是符号放错或者不匹配  if (!pe)  {  printf("Error: parentheses mismatched\n");  return false;  }  // 左括号出栈且不放入输出队列  sl--;  // 扫描完左括号后   // 如果栈顶元素是函数运算符  // 则将其出栈并放入输出队列  if (sl > 0)  {  sc = stack[sl - 1];  if (is_function(sc))  {  *outpos = sc;  ++outpos;  sl--;  }  }  }  //未知运算符c  else printf("Unknown token %c\n", c);  }  ++strpos;  }  // 当所有元素已经读完  // 栈中还有剩余运算符  while (sl > 0)  {  sc = stack[sl - 1];  //如果剩余括号，则符号放错或者不匹配  if (sc == '(' || sc == ')')   {  printf("Error: parentheses mismatched\n");  return false;  }  //出栈并放入输出队列  *outpos = sc;  ++outpos;  --sl;  }  *outpos = 0;//指针置零  return true; } bool execution_order(const char* input)  {  printf("order: (arguments in reverse order)\n");  const char* strpos = input, * strend = input + strlen(input);  char c, res[4];  unsigned int sl = 0, sc, stack[32], rn = 0;  // While there are input tokens left  while (strpos < strend)   {  // Read the next token from input.  c = *strpos;  // If the token is a value or identifier  if (is_ident(c))   {  // Push it onto the stack.  stack[sl] = c;  ++sl;  }  // Otherwise, the token is an operator (operator here includes both operators, and functions).  else if (is_operator(c) || is_function(c))  {  sprintf(res, "_%02d", rn);  printf("%s = ", res);  ++rn;  // It is known a priori that the operator takes n arguments.  unsigned int nargs = op_arg_count(c);  // If there are fewer than n values on the stack  if (sl < nargs ) return false; // (Error) The user has not input sufficient values in the expression.  // Else, Pop the top n values from the stack.  // Evaluate the operator, with the values as arguments.  if (is_function(c))   {  printf("%c(", c);  while (nargs > 0)   {  sc = stack[sl - 1];  sl--;  if (nargs > 1) printf("%s, ", &sc);  else printf("%s)\n", &sc);  --nargs;  }  }  else   {  if (nargs == 1)   {  sc = stack[sl - 1];  sl--;  printf("%c %s;\n", c, &sc);  }  else  {  sc = stack[sl - 1];  sl--;  printf("%s %c ", &sc, c);  sc = stack[sl - 1];  sl--;  printf("%s;\n", &sc);  }  }  // Push the returned results, if any, back onto the stack.  stack[sl] = *(unsigned int*)res;  ++sl;  }  ++strpos;  }  // If there is only one value in the stack  // That value is the result of the calculation.  if (sl == 1)   {  sc = stack[sl - 1];  sl--;  printf("%s is a result\n", &sc);  return true;  }  // If there are more values in the stack  // (Error) The user input has too many values.  return false; } int main() {  // functions: A() B(a) C(a, b), D(a, b, c) ...  // identifiers: 0 1 2 3 ... and a b c d e ...  // operators: = - + / * % !  const char* input = "a = D(f - b * c + d, !e, g)";  char output[128];  printf("input: %s\n", input);  if (shunting_yard(input, output))   {  printf("output: %s\n", output);  if (!execution_order(output))  printf("\nInvalid input\n");  }  return 0; } 

参见

• 中缀表达式
• 后缀表达式