調度場算法
算法
此條目沒有列出任何參考或來源。 (2014年2月8日) |
調度場算法（Shunting Yard Algorithm）是一個用於將中綴表達式轉換為後綴表達式的經典算法，由艾茲格·迪傑斯特拉引入，因其操作類似於火車編組場而得名。
簡例
編輯
- 輸入：3+4
通過這個例子可以看出兩條規則：
- 當讀入一個數字時直接入輸出隊列
- 當輸入結束後，運算符隊列中所有操作符入輸出隊列
詳細的算法
編輯- 當還有記號可以讀取時：
- 讀取一個記號。
- 如果這個記號表示一個數字，那麼將其添加到輸出隊列中。
- 如果這個記號表示一個函數，那麼將其壓入棧當中。
- 如果這個記號表示一個函數參數的分隔符（例如，一個半角逗號
,）：
- 從棧當中不斷地彈出操作符並且放入輸出隊列中去，直到棧頂部的元素為一個左括號為止。如果一直沒有遇到左括號，那麼要麼是分隔符放錯了位置，要麼是括號不匹配。
- 如果這個記號表示一個操作符，記做o1，那麼：
- 只要存在另一個記為o2的操作符位於棧的頂端，並且
- 如果o1是左結合性的並且它的運算符優先級要小於或者等於o2的優先級，或者
- 如果o1是右結合性的並且它的運算符優先級比o2的要低，那麼
- 將o2從棧的頂端彈出並且放入輸出隊列中（循環直至以上條件不滿足為止）；
- 然後，將o1壓入棧的頂端。
- 如果這個記號是一個左括號，那麼就將其壓入棧當中。
- 如果這個記號是一個右括號，那麼：
- 從棧當中不斷地彈出操作符並且放入輸出隊列中，直到棧頂部的元素為左括號為止。
- 將左括號從棧的頂端彈出，但並不放入輸出隊列中去。
- 如果此時位於棧頂端的記號表示一個函數，那麼將其彈出並放入輸出隊列中去。
- 如果在找到一個左括號之前棧就已經彈出了所有元素，那麼就表示在表達式中存在不匹配的括號。
- 當再沒有記號可以讀取時：
- 如果此時在棧當中還有操作符：
- 如果此時位於棧頂端的操作符是一個括號，那麼就表示在表達式中存在不匹配的括號。
- 將操作符逐個彈出並放入輸出隊列中。
- 退出算法。
更詳細的例子
編輯
| 輸入 | 動作 | 輸出 (逆波蘭表示法) | 運算符堆棧 | 提示 |
|---|---|---|---|---|
| 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;
}