基本介紹
- 中文名：調度場算法
- 外文名：Shunting Yard Algorithm
詳細的算法,C++程式實現,
詳細的算法
- 當還有記號可以讀取時：
- 讀取一個記號。
- 如果這個記號表示一個數字，那么將其添加到輸出佇列中。
- 如果這個記號表示一個函式，那么將其壓入棧當中。
- 如果這個記號表示一個函式參數的分隔設定（例如，一個半角逗號,）：
- 從棧當中不斷地彈出操作符並且放入輸出佇列中去，直到棧頂部的元素為一個左括弧為止。如果一直沒有遇到左括弧，那么要么是分隔設定放錯了位置，要么是括弧不匹配。
- 如果這個記號表示一個操作符，記做o1，那么：
- 只要存在另一個記為o2的操作符位於棧的頂端，並且
- 如果o1是左結合性的並且它的運算符優先權要小於或者等於o2的優先權，或者
- 如果o1是右結合性的並且它的運算符優先權比o2的要低，那么
- 將o2從棧的頂端彈出並且放入輸出佇列中（循環直至以上條件不滿足為止）；
- 然後，將o1壓入棧的頂端。
- 如果這個記號是一個左括弧，那么就將其壓入棧當中。
- 如果這個記號是一個右括弧，那么：
- 從棧當中不斷地彈出操作符並且放入輸出佇列中，直到棧頂部的元素為左括弧為止。
- 將左括弧從棧的頂端彈出，但並不放入輸出佇列中去。
- 如果此時位於棧頂端的記號表示一個函式，那么將其彈出並放入輸出佇列中去。
- 如果在找到一個左括弧之前棧就已經彈出了所有元素，那么就表示在表達式中存在不匹配的括弧。
- 當再沒有記號可以讀取時：
- 如果此時在棧當中還有操作符：
- 如果此時位於棧頂端的操作符是一個括弧，那么就表示在表達式中存在不匹配的括弧。
- 將操作符逐個彈出並放入輸出佇列中。
- 退出算法。
C++程式實現
#include <cstring>#include <cstdio>// 操作符// 優先權 符號 運算順序// 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;}#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'))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(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; } } // 如果輸入符號為操作符，op1，然後: else if(is_operator(c)) { while(sl > 0) { sc = stack[sl - 1]; // While there is an operator token, o2, at the top of the stack // op1 is left-associative and its precedence is less than or equal to that of op2, // or op1 is right-associative and its precedence is less than that of op2, if(is_operator(sc) && ((op_left_assoc(c) && (op_preced(c) <= op_preced(sc))) || (!op_left_assoc(c) && (op_preced(c) < op_preced(sc))))) { // Pop o2 off the stack, onto the output queue; *outpos = sc; ++outpos; sl--; } else { break; } } // push op1 onto the stack. stack[sl] = c; ++sl; } // If the token is a left parenthesis, then push it onto the stack. else if(c == '(') { stack[sl] = c; ++sl; } // If the token is a right parenthesis: else if(c == ')') { bool pe = false; // Until the token at the top of the stack is a left parenthesis, // pop operators off the stack onto the output queue while(sl > 0) { sc = stack[sl - 1]; if(sc == '(') { pe = true; break; } else { *outpos = sc; ++outpos; sl--; } } // If the stack runs out without finding a left parenthesis, then there are mismatched parentheses. if(!pe) { printf("Error: parentheses mismatched\n"); return false; } // Pop the left parenthesis from the stack, but not onto the output queue. sl--; // If the token at the top of the stack is a function token, pop it onto the output queue. if(sl > 0) { sc = stack[sl - 1]; if(is_function(sc)) { *outpos = sc; ++outpos; sl--; } } } else { printf("Unknown token %c\n", c); return false; // Unknown token } } ++strpos; } // When there are no more tokens to read: // While there are still operator tokens in the stack: while(sl > 0) { sc = stack[sl - 1]; if(sc == '(' || sc == ')') { printf("Error: parentheses mismatched\n"); return false; } *outpos = sc; ++outpos; --sl; } *outpos = 0; // Null terminator 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 stackif(sl < nargs) {// (Error) The user has not input sufficient values in the expression.return false;}// 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;}