C++ 数据机构转化
中缀表达式
中缀表达式是在两个操作数之间写入哪个运算符(+,-,*,/)。例如,考虑以下表达式:
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;
}
输出: