調度場算法

維基百科,自由的百科全書
跳至導覽 跳至搜尋

調度場算法(Shunting Yard Algorithm)是一個用於將中綴表達式轉換為後綴表達式的經典算法,由艾茲格·迪傑斯特拉引入,因其操作類似於火車編組場而得名。

簡例[編輯]

算法示意圖,使用了3個空間。輸入用符號代替,如果輸入是一個數字則直接進輸出隊列,即圖中 b),d),f),h)。如果輸入是運算符,則壓入操作符堆棧,即圖中 c),e),但是,如果輸入運算符的優先級低於或等於運算符棧頂的操作符優先級,則棧內元素進入輸出隊列,輸入操作符壓入運算符堆棧,即圖中 g)。 最後,運算符堆棧內元素入輸出隊列,算法結束.
輸入:3+4
  1. 將3入輸出隊列(每當輸入一個數字時,直接進入輸出隊列)
  2. 將+號壓入運算堆棧
  3. 將4入輸出隊列
  4. 輸入結束,將操作符堆棧中剩餘操作符入輸出隊列
  5. 在本情況下只有+號
  6. 輸出 3 4 +

通過這個例子可以看出兩條規則:

  • 當讀入一個數字時直接入輸出隊列
  • 當輸入結束後,運算符隊列中所有操作符入輸出隊列

詳細的算法[編輯]

  • 當還有記號可以讀取時:
  • 讀取一個記號。
  • 如果這個記號表示一個數字,那麼將其添加到輸出隊列中。
  • 如果這個記號表示一個函數,那麼將其壓入棧當中。
  • 如果這個記號表示一個函數參數的分隔符(例如,一個半角逗號 , ):
  • 從棧當中不斷地彈出操作符並且放入輸出隊列中去,直到棧頂部的元素為一個左括號為止。如果一直沒有遇到左括號,那麼要麼是分隔符放錯了位置,要麼是括號不匹配。
  • 如果這個記號表示一個操作符,記做o1,那麼:
  • 只要存在另一個記為o2的操作符位於棧的頂端,並且
如果o1是左結合性的並且它的運算符優先級要小於或者等於o2的優先級,或者
如果o1是右結合性的並且它的運算符優先級比o2的要低,那麼
將o2從棧的頂端彈出並且放入輸出隊列中(循環直至以上條件不滿足為止);
  • 然後,將o1壓入棧的頂端。
  • 如果這個記號是一個左括號,那麼就將其壓入棧當中。
  • 如果這個記號是一個右括號,那麼:
  • 從棧當中不斷地彈出操作符並且放入輸出隊列中,直到棧頂部的元素為左括號為止。
  • 將左括號從棧的頂端彈出,但並不放入輸出隊列中去。
  • 如果此時位於棧頂端的記號表示一個函數,那麼將其彈出並放入輸出隊列中去。
  • 如果在找到一個左括號之前棧就已經彈出了所有元素,那麼就表示在表達式中存在不匹配的括號。
  • 當再沒有記號可以讀取時:
  • 如果此時在棧當中還有操作符:
  • 如果此時位於棧頂端的操作符是一個括號,那麼就表示在表達式中存在不匹配的括號。
  • 將操作符逐個彈出並放入輸出隊列中。
  • 退出算法。

更詳細的例子[編輯]

  • 中綴表示法 及 結果:
    逆波蘭表示法: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>

// 操作符
// 优先级		符号		运算顺序
// 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 stack
			if(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;
}

參見[編輯]