C++ 数据机构转化基础教程文档
收录于 2023-04-20 00:10:05 · بالعربية · English · Español · हिंदीName · 日本語 · Русский язык · 中文繁體
中缀表达式
中缀表达式是在两个操作数之间写入哪个运算符(+,-,*,/)。例如,考虑以下表达式:
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-
使用堆栈将中缀转换为后缀表达式的算法
以下是算法将中缀表达式转换为反向波兰语符号的算法。
初始化堆栈。
在中缀表达式中从左到右扫描运算符。
如果最左边的字符是操作数,请将其设置为Postfix字符串的当前输出。
如果扫描的字符是运算符,并且堆栈为空或包含'(',')'符号,则将运算符推入堆栈。
如果扫描的运算符的优先级高于堆栈中现有的优先级运算符,或者如果堆栈为空,则将其放在堆栈中。
如果扫描的运算符的优先级低于堆栈中现有的运算符,请弹出所有堆栈运算符。之后,将扫描的运算符推入堆栈。
如果扫描的字符是左括号'(',则将其推入堆栈。
如果遇到右括号')',则弹出堆栈并打印所有输出字符串,直到遇到'('并丢弃两个括号。
重复从2到8的所有步骤,直到扫描中缀表达式为止。
打印堆栈输出。
从堆栈中弹出并输出所有字符,包括运算符,直到不为空为止。
让我们将一个中缀表达式转换为堆栈中的后缀表达式:
在这里,我们有中缀表达式((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; // defines the boolean function for operator, operand, equalOrhigher precedence and the string conversion function. 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 Infix expression 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; } // define the IsOperator() function to validate whether any symbol is operator. /* if the symbol is operator, it returns true, otherwise false. */ bool IsOperator(char c) { if(c == '+' || c == '-' || c == '*' || c == '/' || c == '^' ) return true; return false; } // IsOperand() function is used to validate whether the character is operand. bool IsOperand(char c) { if( c >= 'A' && c <= 'Z') /* Define the character in between A to Z. if not, it returns false.*/ return true; if (c >= 'a' && c <= 'z') // Define the character in between a to z. if not, it returns false. */ return true; if(c >= '0' && c <= '9') // Define the character in between 0 to 9. if not, it returns false. */ return true; return false; } // here, precedence() function is used to define the precedence to the operator. int precedence(char op) { if(op == '+' || op == '-') /* it defines the lowest precedence */ return 1; if (op == '*' || op == '/') return 2; if(op == '^') /* exponent operator has the highest precedence * return 3; return 0; } /* The eqlOrhigher() function is used to check the higher or equal precedence of the two operators in infix expression. */ 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() function is used to convert the infix expression to the postfix expression of the 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; }
输出: