前缀表达式是在两个操作数之间写入运算符(+,-,*,/)的表达式。例如,考虑以下表达式:
A + B A + B - C (A + B) + (C - D)
在这里,我们在操作数A和B之间编写了'+'运算符,并在C和D操作数之间编写了-运算符。
后缀运算符还包含运算符和操作数。在后缀表达式中,运算符写在操作数之后。也称为反向波兰符号。例如,考虑以下表达式:
A B + A B + C - A B C * + A B + C * D -
以下是算法,用于将中缀表达式转换为反向波兰语表示法。
让我们将一个中缀表达式转换为堆栈中的后缀表达式:
来源:LearnFk无涯教程网
在这里,我们有中缀表达式((A *(B + D)/ E)-F *(G + H/K)))转换为其等效的后缀表达式:
标签号 | 已扫描符号 | 堆栈 | 表达式 |
---|---|---|---|
1 | ( | ( | |
2 | ( | (( | |
3 | A | (( | A |
4 | * | ((* * ) | A |
5 | ( | ((*()) | A |
6 | B | ((*()) | AB |
7 | + | (((*(+ ))) | AB |
8 | D | (((*(+ ))) | ABD |
9 | ) | ((* * ) | ABD + |
10 | / | ((* * ) | ABD + |
11 | E | ((* * ) | ABD + E |
12 | ) | ( | ABD + E/* |
13 | - | (- | ABD + E/* |
14 | ( | (-( | ABD + E/* |
15 | F | (-( | ABD + E/* F |
16 | * | (-(* ) | ABD + E/* F |
17 | ( | (-(*()) | ABD + E/* F |
18 | G | (-(*()) | ABD + E/* FG |
19 | + | (-(*(+ )) | ABD + E/* FG |
20 | H | (-(*(+ )) | ABD + E/* FGH |
21 | / | (-(*(+/)) | ABD + E/* FGH |
22 | K | (-(*(+/)) | ABD + E/* FGHK |
23 | ) | (-(* ) | ABD + E/* FGHK/+ |
24 | ) | (- | ABD + E/* FGHK/+ * |
25 | ) | ABD + E/* FGHK/+ *- |
让我们创建一个C++程序,将中缀表达式转换为后缀表达式
#include<iostream> #include<stack> using namespace std; // 定义运算符、操作数、equalOrhigher 优先级的布尔函数和字符串转换函数。 bool IsOperator(char); bool IsOperand(char); bool eqlOrhigher(char, char); string convert(string); int main() { string infix_expression, postfix_expression; int ch; do { cout << " Enter an infix expression: "; cin >> infix_expression; postfix_expression = convert(infix_expression); cout << "\n Your 中缀表达式 is: " << infix_expression; cout << "\n Postfix expression is: " << postfix_expression; cout << "\n \t Do you want to enter infix expression (1/ 0)?"; cin >> ch; //cin.ignore(); } while(ch == 1); return 0; } // 定义 IsOperator() 函数来验证是否有任何符号是运算符。 /* 如果符号是运算符,则返回 true,否则返回 false。 */ bool IsOperator(char c) { if(c == '+' || c == '-' || c == '*' || c == '/' || c == '^' ) return true; return false; } // IsOperand() 函数用于验证字符是否为操作数。 bool IsOperand(char c) { if( c >= 'A' && c <= 'Z') /* 定义 A 到 Z 之间的字符。如果不是,则返回 False。*/ return true; if (c >= 'a' && c <= 'z') //定义 a 到 z 之间的字符。如果不是,则返回 False。 */ return true; if(c >= '0' && c <= '9') //将字符定义在 0 到 9 之间。如果不是,则返回 False。 */ return true; return false; } // 在这里,precedence() 函数用于定义运算符的优先级。 int precedence(char op) { if(op == '+' || op == '-') /* 它定义了最低优先级 */ return 1; if (op == '*' || op == '/') return 2; if(op == '^') /* 指数运算符具有最高优先级 */ return 3; return 0; } /* eqlOrhigher() 函数用于检查中缀表达式中两个运算符的更高或相等优先级。 */ bool eqlOrhigher (char op1, char op2) { int p1 = precedence(op1); int p2 = precedence(op2); if (p1 == p2) { if (op1 == '^' ) return false; return true; } return (p1>p2 ? true : false); } /* string convert() 函数用于将中缀表达式转换为 Stack 的后缀表达式 */ string convert(string infix) { stack <char> S; string postfix =""; char ch; S.push( '(' ); infix += ')'; for(int i = 0; i<infix.length(); i++) { ch = infix[i]; if(ch == ' ') continue; else if(ch == '(') S.push(ch); else if(IsOperand(ch)) postfix += ch; else if(IsOperator(ch)){ while(!S.empty() && eqlOrhigher(S.top(), ch)){ postfix += S.top(); S.pop(); } S.push(ch); }else if(ch == ')'){ while(!S.empty() && S.top() != '('){ postfix += S.top(); S.pop(); } S.pop(); } } return postfix; }
输出:
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)