Mixing
调度场算法
调度场算法（Shunting Yard Algorithm）是一个用于将中缀表达式转换为后缀表达式的经典算法，由艾兹格·迪杰斯特拉引入，因其操作类似于火车编组场而得名。
目录
1 簡例
2 详细的算法
3 更详细的例子
4 C++程序实现
5 参见
簡例
算法示意图，使用了3个空间。输入用符号代替，如果输入是一个数字则直接进输出队列，即图中 b),d),f),h)。如果输入是运算符，则压入操作符堆栈，即图中 c),e)，但是，如果输入运算符的优先级低于或等于运算符栈顶的操作符优先级，则栈内元素进入输出队列，输入操作符压入运算符堆栈，即图中 g)。 最后，运算符堆栈内元素入输出队列，算法结束.
- 输入：3+4
- 将3入输出队列(每当输入一个数字时，直接进入输出队列)
- 将+号压入运算堆栈
- 将4入输出队列
- 输入结束，将操作符堆栈中剩余操作符入输出队列
- 在本情况下只有+号
- 输出 3 4 +
通过这个例子可以看出两条规则：
- 当读入一个数字时直接入输出队列
- 当输入结束后，运算符队列中所有操作符入输出队列
详细的算法
- 当还有记号可以读取时：
- 读取一个记号。
- 如果这个记号表示一个数字，那么将其添加到输出队列中。
- 如果这个记号表示一个函数，那么将其压入栈当中。
- 如果这个记号表示一个函数参数的分隔符（例如，一个半角逗号
,）：
- 从栈当中不断地弹出操作符并且放入输出队列中去，直到栈顶部的元素为一个左括号为止。如果一直没有遇到左括号，那么要么是分隔符放错了位置，要么是括号不匹配。
- 如果这个记号表示一个操作符，记做o1，那么：
- 只要存在另一个记为o2的操作符位于栈的顶端，并且
- 如果o1是左结合性的并且它的运算符优先级要小于或者等于o2的优先级，或者
- 如果o1是右结合性的并且它的运算符优先级比o2的要低，那么
- 将o2从栈的顶端弹出并且放入输出队列中（循环直至以上条件不满足为止）；
- 然后，将o1压入栈的顶端。
- 如果这个记号是一个左括号，那么就将其压入栈当中。
- 如果这个记号是一个右括号，那么：
- 从栈当中不断地弹出操作符并且放入输出队列中，直到栈顶部的元素为左括号为止。
- 将左括号从栈的顶端弹出，但并不放入输出队列中去。
- 如果此时位于栈顶端的记号表示一个函数，那么将其弹出并放入输出队列中去。
- 如果在找到一个左括号之前栈就已经弹出了所有元素，那么就表示在表达式中存在不匹配的括号。
- 当再没有记号可以读取时：
- 如果此时在栈当中还有操作符：
- 如果此时位于栈顶端的操作符是一个括号，那么就表示在表达式中存在不匹配的括号。
- 将操作符逐个弹出并放入输出队列中。
- 退出算法。
更详细的例子
中綴表示法 及 結果：3+4×2÷(1−5)23{displaystyle {{3}+{{{4}times {2}}div {{left({{1}-{5}}right)}^{{2}^{3}}}}}}={displaystyle ,=,}
3.0001220703125{displaystyle 3.0001220703125}
逆波兰表示法：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 mismatchedn");
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 mismatchedn");
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 %cn", 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 mismatchedn");
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 resultn", &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: %sn", input);
if(shunting_yard(input, output)) {
printf("output: %sn", output);
if(!execution_order(output))
printf("nInvalid inputn");
}
return 0;
}
参见
- 中缀表达式
- 后缀表达式
Comments
Post a Comment