There are many and detailed reference materials on the dispatch field algorithm on the Internet; and there are other methods to deal with the problem of converting infix expressions into prefix/suffix expressions processed by the dispatch field algorithm. Those who are interested can learn about it on their own.
References:
Algorithm – Shunting Yard Algorithm – Tencent Cloud Developer Community – Tencent Cloud (tencent.com)
Prefix, infix, suffix expressions (reverse Polish expression) – chensongxian – Blog Garden (cnblogs.com)
Prefix expressions, infix expressions and postfix expressions – Return by the Moon – Blog Garden (cnblogs.com)
1. Preliminary summary
| Prefix expression (Polish style) | Operator before the operand |
| Infix expression (common) | Operator in the middle of the operands |
| Postfix expression (reverse polish) | Operator after the operand |
Before talking about the scheduling yard algorithm, we first introduce the concepts of the above three algorithm expressions.
The dispatch yard algorithm is mainly used to convert infix expressions into prefix/postfix expressions.
Here we first look at the conversion example of (A – B) * C + D / E:
Convert to prefix expression:
- First calculate A – B and convert to – A B
- – A B is then calculated with C and converted to * – A B C
- Then calculate D / E and convert to / D E
- Finally add the two and convert to + * – A B C / D E
Convert to postfix expression:
- First calculate A – B and convert to A B –
- A B – is then calculated with C to convert to A B – C *
- Then calculate D / E and convert to D E /
- Finally add the two and convert to A B – C * D E / +
2. Algorithmic thinking
Stack is mainly used here.
Generally speaking, according to the precedence of operators, we adopt the following ideas:
Scan and read in order: output directly when encountering operands; when encountering an operator, compare the priority of the operator and the operator on the top of the stack according to the comparison rules of prefix/suffix expressions and perform corresponding operations (change the top of the stack The operator outputs and pops it from the stack until the stack is empty or the condition is not met, and then the operator is pushed onto the stack). After processing is completed, read out in the specified order.
Here, we need to pay special attention to the handling of brackets:
The priority of parentheses is generally the highest, but in the scheduling field algorithm, it is neither feasible nor correct to simply treat parentheses as an operator with the highest priority.
Here we need to take out the left and right brackets for special processing based on the original idea; at the same time, it needs to be clear that there are no brackets in the prefix/suffix expression, so the brackets should not be output.
The following takes the idea of converting infix expressions into postfix expressions as an example:
(1) Initialize two stacks: the operator stack symbol and the stack operand that stores intermediate results;
(2) Scan infix expressions from left to right;
(3) When the operand is encountered, push it into operand;
(4) When an operator is encountered, compare its priority with the operator on the top of the symbol stack:
(4-1) If symbol is empty, or the operator on the top of the stack is the left bracket “(“, then this operator is pushed directly onto the stack;
(4-2) Otherwise, if the priority is higher than the operator on the top of the stack, the operator will also be pushed into symbol;
(4-3) Otherwise, pop the operator on the top of the symbol stack and push it into operand, and go to (4-1) again to compare with the new top operator on the stack in symbol;
(5) When encountering parentheses:
(5-1) If it is the left bracket “(“, press the symbol directly;
(5-2) If it is a right bracket “)”, pop up the operators on the top of the symbol stack in turn, and push operand until the left bracket is encountered, at which time the pair of brackets will be discarded;
(6) Repeat steps (2) to (5) until the rightmost part of the expression;
(7) Pop the remaining operators in symbol one by one and push them into operand;
(8) Pop out the elements in operand in turn and output them. The reverse order of the results is the suffix expression corresponding to the infix expression.
Note: The conversion process of prefix expressions is basically the same as that of suffixes, mainly reflected in the following three differences:
- When converting to a postfix expression, the infix expression is traversed from left to right; the prefix expression is traversed from right to left, and the left and right brackets encountered in this process should be processed in reverse, such as the ReverseExp function in the code;
- When judging the priority of the operator and the operator on the top of the stack, the postfix expression means that when the operator priority is greater than the priority of the operator on the top of the stack, the operator is directly pushed onto the stack; the prefix expression is greater than or equal to;
- After getting the final intermediate result stack (operand in the code), the elements of operand are popped up in sequence and output is the prefix expression; the reverse order of the results of operand popped up in sequence is the suffix expression.
For details, please refer to the following two functions ConvertPolish and ConvertReversePolish to compare the differences.
The code also adds the definition of operator priority and the judgment return function, the operator judgment function, and the flip function of the string according to the prefix expression traversal requirements from right to left.
The code examples are only for infix expressions containing addition, subtraction, multiplication, division, and left and right parentheses.
#include<iostream>
#include<stack>
using namespace std;
//return operator priority
int Priority(char sym)
{
int priority;
switch (sym)
{
case' + ':priority = 1; break;
case'-':priority = 1; break;
case'*':priority = 2; break;
case'/':priority = 2; break;
default:priority = 0; break;
}
return priority;
}
//Determine whether the character is an operator
bool isOperator(char ch)
{
if (ch == '(' || ch == ')' || ch == ' + ' || ch == '-' || ch == '*' || ch == '/')
return true;
return false;
}
//Flip the string and require the left and right brackets to be replaced
string ReverseExp(string exp)
{
string exp_;
for (int i = exp.length() - 1; i >= 0; i--) {
if (exp[i] == '(')
{
exp_ + = ')';
}
else if (exp[i] == ')')
{
exp_ + = '(';
}
else
{
exp_ + = exp[i];
}
}
return exp_;
}
//Convert infix expression to prefix expression (right to left)
stack<char> ConvertPolish(string exp)
{
stack<char>symbol;
stack<char>operand;
// flip expression
exp = ReverseExp(exp);
int i = 0;
char ch, sym;
ch = exp[i];
while (ch != '\0')
{
//If it is an operator
if (isOperator(ch))
{
//When encountering a parenthesis, if it is a left parenthesis, push the symbol directly
if (ch == '(')
{
symbol.push(ch);
i + + ;
ch = exp[i];
}
//If it is a right parenthesis, pop up the top elements of the symbol stack and push operand until the left parenthesis is encountered.
else if (ch == ')')
{
while (symbol.top() != '(')
{
operand.push(symbol.top());
symbol.pop();
}
symbol.pop();
i + + ;
ch = exp[i];
}
//If it is an operator with listed precedence
else
{
//If symbol is empty, or the operator on the top of the stack is the left bracket "(", push this operator directly onto the stack
if (symbol.empty() == true || symbol.top() == '(')
{
symbol.push(ch);
}
//Otherwise, if the operator's priority is lower than the operator on the top of the stack, pop the operator on the top of the symbol stack and push it into operand, and then compare the operator with the new top operator on the stack in symbol.
//If the priority of the operator is greater than or equal to the operator on the top of the stack, directly push the operator onto the stack
else
{
sym = symbol.top();
while (Priority(sym) > Priority(ch))
{
operand.push(symbol.top());
symbol.pop();
if (symbol.empty())
{
break;
}
sym = symbol.top();
}
symbol.push(ch);
}
i + + ;
ch = exp[i];
}
}
//If it is an operand. Press directly into operand
else
{
operand.push(ch);
i + + ;
ch = exp[i];
}
}
//Take out the remaining operators in symbol and push them into operand.
while (!symbol.empty())
{
operand.push(symbol.top());
symbol.pop();
}
return operand;
}
//Convert infix expression to postfix expression (from left to right)
stack<char> ConvertReversePolish(string exp)
{
stack<char>symbol;
stack<char>operand;
stack<char>result;
int i = 0;
char ch, sym;
ch = exp[i];
while (ch != '\0')
{
//If it is an operator
if (isOperator(ch))
{
//When encountering a parenthesis, if it is a left parenthesis, press the symbol directly
if (ch == '(')
{
symbol.push(ch);
i + + ;
ch = exp[i];
}
//If it is a right parenthesis, pop up the top elements of the symbol stack and push operand until the left parenthesis is encountered.
else if (ch == ')')
{
while (symbol.top() != '(')
{
operand.push(symbol.top());
symbol.pop();
}
symbol.pop();
i + + ;
ch = exp[i];
}
//If it is an operator with listed precedence
else
{
//If symbol is empty, or the operator on the top of the stack is the left bracket "(", push this operator directly onto the stack
if (symbol.empty() == true || symbol.top() == '(')
{
symbol.push(ch);
}
//Otherwise, if the priority of the operator is less than or equal to the operator on the top of the stack, pop the operator on the top of the symbol stack and push it into operand, and then compare the operator with the new operator on the top of the stack in symbol.
//If the priority of this operator is greater than the operator on the top of the stack, directly push this operator onto the stack
else
{
sym = symbol.top();
while (Priority(sym) >= Priority(ch))
{
operand.push(symbol.top());
symbol.pop();
if (symbol.empty())
{
break;
}
sym = symbol.top();
}
symbol.push(ch);
}
i + + ;
ch = exp[i];
}
}
//If it is an operand. Press directly into operand
else
{
operand.push(ch);
i + + ;
ch = exp[i];
}
}
//Take out the remaining operators in symbol and push them into operand.
while (!symbol.empty())
{
operand.push(symbol.top());
symbol.pop();
}
//Output in reverse order
while (!operand.empty())
{
result.push(operand.top());
operand.pop();
}
return result;
}
int main()
{
string exp;
cout << "Please enter the infix expression:";
cin >> exp;
cout << "The converted prefix expression is: ";
stack<char>prefix_res = ConvertPolish(exp);
while (!prefix_res.empty())
{
char r;
r = prefix_res.top();
prefix_res.pop();
cout << r;
}
cout << endl;
cout << "The converted suffix expression is: ";
stack<char>suffix_res = ConvertReversePolish(exp);
while (!suffix_res.empty())
{
char r;
r = suffix_res.top();
suffix_res.pop();
cout << r;
}
return 0;
}
The running results are as follows:
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57389 people are learning the system