If stacks and queues are not clear, take a look at chapter 2 of data Structures in this blog, Stacks and queues.
1. Output sequence
1. 1. , n, out: P1, P2… , pn.
If PI = n (1 < I < n)?
Conclusion: PI + 1 > > PI… > pn. Since PI =n, we can see that the push is complete, and since 1< I
1, 2… , n, out: P1, P2… , pn.
If I <j<k, what is the relationship between the sizes of PI, Pj and PK?PI, Pj, PK, all of that6 kinds of
All permutations of 3.We can treat I,j,k as 1,2,3, and the loading data as 1,2,3, so the unloading is P1, P2,p3.
(1) 1 2 3 (2) 1 3 2 (3) 2 1 3 (4) 2 3 1 (5) 3 1 2 (6) 3 2 1
Whether we, in turn, can they see the stack to complete (1) 1, 1, 2, 2, 3, 3 (2) 1, 1, 2, 3, 3, 2 (3) 1, 2, 2, 1, 3, 3 (4) 1, 2, 2, 3, 3, 1 out of (5) obviously cannot succeed (6) 1, 2, Three in, three out, two out, one out
The fifth is unsuccessful, and the size relationship is: Pj < PK < PI
Conclusion: The size relation cannot be determined by the number of stack sequences pj< PK < PI, which can be determined by the Cattelan number.
3. Catalan Number
Cn=(2n)! /[(n+1)!n!] When n numbers are pushed in some order and can be pushed out at any time, the number of different stack sequences is Cn.
2. Expression conversion ideas
Three expressions: infix, prefix (operator first), and suffix (operator last).
Priority diagram for operators:A smaller value indicates a higher priority
.
1. Infix prefix
Step 1: Pass all operations between operands and operators through parentheses based on their precedenceenclosed
.
Step 2: Place all operators in the current parenthesisIn front of the
.Step 3: RemoveAll braces
.
2. Suffix to suffix
Step 1: Pass all operations between operands and operators through parentheses based on their precedenceenclosed
.
Step 2: Place all operators after the current parentheses.
Step 3: Remove all parentheses
3. Suffix to infix
Scan from front to back, find the first operator, and place the operator in the operandIn the middle
“And then put them in parentheses. Then do the same in turn. And then finally, we’re done with all the operatorsExtra parentheses
Get rid of.
4. Change from suffix to prefix
Scan from front to back, find the first operator, and place the operator in the operandIn front of the
“And then put them in parentheses. Then do the same in turn. And then finally, we’re done with all the operatorsAll of the
Remove the parentheses.
3. Use stacks to convert between expressions
1. Suffix to suffix
Note the following conditions: 1The operator
. So you have operandsSo let me just write it out
Is pushed only when it encounters an operator. 2. Scanning direction:From left to right
. 3. Conditions for the operator to be pushed off the stack :(1) the priority of the operator if pushed onto the stackLess than or equal to
The priority of the top of the stack (when the current operator is not yet on the stack), then the top element is removed from the stack. For example, the top element of the stack is – and the last entry element is +, because+ and - have the same priority
, the – sign is removed from the stack and the + sign is added to the stack. (2) If an open parenthesis is encountered, thenAll the following operators are pushed
Until theencounter
Right parenthesis. When a close parenthesis is encountered, in orderUnstack operator
Until theencounter
Left parenthesis. 4. After the scan is complete, add it to the stackThe remaining operators go off the stack in turn
. Code:
#include <bits/stdc++.h> using namespace std; # define maxSize 10 / / priority comparison, here I only +, *, /,,,, if you need other, can set the int getPriority char (r) {if (r = = '+' | | r = = '-') {return 0; }else if(r=='*'||r=='/'){ return 2; }else{ return 1; }} //infix is the array of infix data, s2 is the array of infix data after conversion, Void infixToPostFix(char infix[],char s2[],int &top2){char s1[maxSize]; int top1=-1; int i=0; While (infix[I]! = '\ 0') {/ / a < = and < = z because I here the incoming data into a, b, c, d, etc., if you are introduced to digital, If may be removed (' a '< = infix [I] && infix [I] < =' z '| | (' 0' < = infix [I] && infix [I] < = '9')) {[+ + ranked by] = s2 infix [I]; ++i; } else if(infix[i]=='('){ s1[++top1]='('; ++i; } else if(infix[i]=='+'||infix[i]=='-'||infix[i]=='*'||infix[i]=='/'){ if(top1==-1||s1[top1]=='('||getPriority(infix[i])>getPriority(s1[top1])){ s1[++top1]=infix[i]; ++i; }else{ s2[++top2]=s1[top1--]; } } else if(infix[i]==')'){ while(s1[top1]! ='('){ s2[++top2]=s1[top1--]; } --top1; // prevent '(' from being added to the stack. ++i; }} while(top1! =-1){ s2[++top2]=s1[top1--]; } } int main(){ char infix[]={0}; char s2[20]; int top2=-1; String name="a+b-a*((c+d)/e-f)+g"; strcpy(infix , name.c_str()); infixToPostFix(infix,s2,top2); // The character array is converted to string name1; name1=s2; cout<<name1<<endl; }Copy the code
Results:
2. Infix prefix
Note the following conditions: 1. The stack stores operators. So when you see an operand, you write it out, and when you see an operator, you push it. 2. Scanning direction: right to left. 3. Conditions for removing operators from the stack :(1) if the priority of the push operator is less than that of the top of the stack (the current operator is not yet on the stack), then the top element is removed from the stack. For example, if the top element is * and the next entry element is -, the priority of the – is lower than that of the top *, the * is removed from the stack and the – is added to the stack. (2) If a close parenthesis is encountered, all subsequent operators are pushed until an open parenthesis is encountered. When an open parenthesis is encountered, the stack operators are unrolled until a close parenthesis is encountered. 4. After scanning, remove the remaining operators from the stack one by one.
Code:
#include <bits/stdc++.h> using namespace std; # define maxSize 10 / / priority judging int getPriority char (r) {if (r = = '+' | | r = = '-') {return 0; }else if(r=='*'||r=='/'){ return 2; }else{ return 1; } } void infixToPostFix(char infix[],char s2[],int &top2){ char s1[maxSize]; int top1=-1; Int I =strlen(infix)-1; / / when I < 0, the scan is complete while (I > = 0) {if (' a '< = infix [I] && infix [I] < =' z '| | (' 0' < = infix [I] && infix [I] < = '9')) {[+ + ranked by] = s2 infix [I]; --i; } else if(infix[i]==')'){ s1[++top1]=')'; --i; } else if(infix[i]=='+'||infix[i]=='-'||infix[i]=='*'||infix[i]=='/'){ if(top1==-1||s1[top1]==')'||getPriority(infix[i])>=getPriority(s1[top1])){ s1[++top1]=infix[i]; --i; }else{ s2[++top2]=s1[top1--]; } } else if(infix[i]=='('){ while(s1[top1]! =')'){ s2[++top2]=s1[top1--]; } --top1; --i; } } while(top1 ! =-1){ s2[++top2]=s1[top1--]; } } int main(){ char infix[]={0}; char s2[20]; int top2=-1; String name="a+b-a*((c+d)/e-f)+g"; strcpy(infix , name.c_str()); infixToPostFix(infix,s2,top2); // String name1; name1=s2; // String reverse(name1.begin(),name1.end())); cout<<name1<<endl; }Copy the code
Results:
3. Suffix to prefix (prefix to suffix is similar)
Scanning from left to right, if it encounters an operator, place the operand after the operator (prefix to suffix and vice versa), because the operator can operate on up to two operands and then combine them as one operand (for example: Ab +, when the + operator is encountered, there are just two operands in front of the operator, a,b, so put the operand after the operator, we get +ab, we can see +ab as an operand), use the combined operand for the next operation, repeat the previous operation, when all the operators have been scanned, Then we can get the prefix expression we need.
4. Use stacks to evaluate expressions
1. Infix expression evaluation
1. Two stacks: one for operands and one for operators. 2. Scanning direction: from left to right. 3. Conditions for operator removal from the stack :(1) if the priority of the pushed operator is less than or equal to the priority of the top of the stack (refers to the top of the stack before the current operator is pushed), then the top element is removed from the stack. For example, if the top element is – and the last entry element is +, because + has the same priority as -, the – sign is removed from the stack and the + sign is pushed onto the stack. (2) If an open parenthesis is encountered, all subsequent operators are pushed until a close parenthesis is encountered. When a close parenthesis is encountered, the stack operators are unrolled until an open parenthesis is encountered. 4. After the operator is removed from the stack, two operands are removed from the stack storing the operands, and then the operands are added to the stack storing the operands. 5. When the scan is complete, the stack of operators is removed in turn. For each operator pushed one operand, the operand is pushed two operands, and the operation is stored on the operand stack. 6. When the operator stack is empty, the value at the bottom of the operand stack is the evaluated value of the infix expression.
Code:
#include <bits/stdc++.h> using namespace std; # define MIN 0.00001 # define maxSize 10 int getPriority (char op) {if op = = '+' | | op = = '-') return 0; else return 1; } int calSub(float opand1,char op,float opand2,float &result){ if(op=='+') result=opand1+opand2; if(op=='-') result=opand1-opand2; if(op=='*') result=opand1*opand2; if(op=='/'){ if(fabs(opand2)<MIN) { return 0; }else{ result=opand1/opand2; } } return 1; } float calInfix(char exp[]){ float s1[maxSize]; int top1=-1; char s2[maxSize]; int top2=-1; int i=0; while(exp[i]! ='\0') { if('0'<=exp[i]&&exp[i]<='9') { s1[++top1]=exp[i]-'0'; // Convert to float with '0' ++ I; } else if(exp[i]=='(') { s2[++top2]='('; ++i; } else if(exp[i]=='+'||exp[i]=='-'||exp[i]=='*'||exp[i]=='/') { if(top2==-1||s2[top2]=='('||getPriority(exp[i])>getPriority(s2[top2])) { s2[++top2]=exp[i]; ++i; } else{ float opand1,opand2,result; char op; int flag; opand2=s1[top1--]; opand1=s1[top1--]; op=s2[top2--]; flag=calSub(opand1,op,opand2,result); if(flag==0) { cout<<"errror"<<endl; return 0; } s1[++top1]=result; } } else if(exp[i]==')') { while(s2[top2]! ='(') { float opand1,opand2,result; char op; int flag; opand2=s1[top1--]; opand1=s1[top1--]; op=s2[top2--]; flag=calSub(opand1,op,opand2,result); if(flag==0){ cout<<"error"<<endl; return 0; } s1[++top1]=result; } --top2; ++i; } } while(top2! =-1){ float opand1,opand2,result; char op; int flag; opand2=s1[top1--]; opand1=s1[top1--]; op=s2[top2--]; flag=calSub(opand1,op,opand2,result); if(flag==0) { cout<<"Error"<<endl; return 0; } s1[++top1]=result; } return s1[top1]; } int main(){ char exp[]={0}; string name="3+4*5*(2+3)"; strcpy(exp,name.c_str()); cout<<calInfix(exp)<<endl; }Copy the code
Results:
2. Evaluate postfix expressions
1. A stack: Used to store operands. 2. Scanning direction:From left to right
. 3. When an operator is encountered, two operands are pushed from the stack, and the operation is performed through the operator and the result is placed on the stack. Repeat in turn. 4. After the scan is complete, the value of the element at the bottom of the stack is the value of the desired suffix expression. Code:
#include <bits/stdc++.h> using namespace std; # define MIN 0.00001 # define maxSize 10 int getPriority (char op) {if op = = '+' | | op = = '-') return 0; else return 1; } int calSub(float opand1,char op,float opand2,float &result){ if(op=='+') result=opand1+opand2; if(op=='-') result=opand1-opand2; if(op=='*') result=opand1*opand2; if(op=='/'){ if(fabs(opand2)<MIN) { return 0; }else{ result=opand1/opand2; } } return 1; } float calPostFix(char exp[]){ float s[maxSize]; int top=-1; int i=0; while(exp[i]! ='\0') { if('0'<=exp[i]&&exp[i]<='9') s[++top]=exp[i]-'0'; else if(exp[i]=='+'||exp[i]=='-'||exp[i]=='*'||exp[i]=='/'){ float opand1,opand2,result; char op; int flag; opand2=s[top--]; opand1=s[top--]; op=exp[i]; flag=calSub(opand1,op,opand2,result); if(flag==0){ cout<<"error"<<endl; return 0; } s[++top]=result; } ++i; } return s[top]; } int main(){ char exp[]={0}; string name="34523+**+"; strcpy(exp,name.c_str()); cout<<calPostFix(exp)<<endl; }Copy the code
Results:
3. Evaluate the prefix expression
1. A stack: Used to store operands. 2. Scanning direction:From right to left
. 3. When an operator is encountered, two operands are pushed from the stack, and the operation is performed through the operator and the result is placed on the stack. Repeat in turn. 4. After the scan is complete, the value of the element at the bottom of the stack is the value of the desired prefix expression.Code:
#include <bits/stdc++.h> using namespace std; # define MIN 0.00001 # define maxSize 10 int getPriority (char op) {if op = = '+' | | op = = '-') return 0; else return 1; } int calSub(float opand1,char op,float opand2,float &result){ if(op=='+') result=opand1+opand2; if(op=='-') result=opand1-opand2; if(op=='*') result=opand1*opand2; if(op=='/'){ if(fabs(opand2)<MIN) { return 0; }else{ result=opand1/opand2; } } return 1; } float calPostFix(char exp[]){ float s[maxSize]; int top=-1; int i=0; for(int i=0; exp[i]! = '\ 0'; ++i) { if('0'<=exp[i]&&exp[i]<='9') s[++top]=exp[i]-'0'; else if(exp[i]=='+'||exp[i]=='-'||exp[i]=='*'||exp[i]=='/'){ float opand1,opand2,result; char op; int flag; opand2=s[top--]; opand1=s[top--]; op=exp[i]; flag=calSub(opand1,op,opand2,result); if(flag==0){ cout<<"error"<<endl; return 0; } s[++top]=result; } } return s[top]; } int main(){ char exp[]={0}; string name="+3*4*5+23"; / / transposed reverse (name. The begin (), the name, the end ()); strcpy(exp,name.c_str()); cout<<calPostFix(exp)<<endl; }Copy the code
Results:
5. The configuration of the circular queue is incorrect
1. Normal configuration
Rear =(rear+1)%maxSize; rear=(rear+1)%maxSize; queue[rear]=x; If (front =(front+1)%maxSize; x=queue[front]; Front =(rear+1)%maxSize = true5. Number of elements in the team :(rear-front+maxSize)%maxSize; (Merge rear greater than front and rear less than front)
2. Abnormal configuration
The first abnormal configuration: change the team entry and exit conditions1. Queue [rear]=x; rear=(rear+1)%maxSize; X =queue[front]; front=(front+1)%maxSize; Abnormal configuration results:The team is fullHow this differs from a normal configuration:In normal configuration, rear is empty. In normal configuration, front is empty.
The second kind of abnormal configuration: change the team empty condition: Empty queue status changes. Empty queue: front==(rear+1)%maxSize is true Abnormal conditions result1. The number of elements is changed: (rear-front+1+maxSize)%maxSize;
Front ==(rear+2)%maxSize is true.
6. Dual-end queues
There are three types of dual-end queues: normal, input restricted, and output restricted.
Normal: Limited input: Output constraints:
1. Which sequence is impossible to output through a two-ended queue with limited input?
We can first calculate the number of impossible sequences by using the Cattelan number (cattelan number output sequence is described there) :Cn=(2n)! /[(n+1)!n!]The number of possible sequences is: C4=14. The number of impossible sequences is: 4! – 14 = 10
The following methods can be used to work out the first queue sequence:
2. Which sequence is impossible to output through a two-ended queue with limited output?
We can first find the number of impossible sequences by the Cattelan number (cattelan number output sequence there is said) : cattelan number formula: Cn=(2n)! /[(n+1)!n!] The number of possible sequences is: C4=14. The number of impossible sequences is: 4! – 14 = 10
I’m going to do the same thing.
7. Stack extension
1. Shared stack
What causes the shared stack?When the top1 stack is full, but top2 has a lot of extra space.
We can share one memory space between the two stacks.This way, you can use the extra memory spaceImplementation of shared stack:1. Exit of shared stack:int stack[maxSize]; int top[2]={-1,maxSize};
2. S1 stack is empty:Top [0] = = 1 is true
When; S2 stack is empty:Top [1] = = maxSize is true
At the right time. 3. S1 into the stack:stack[++top[0]]=x;
S2 into the stack:stack[--top[1]]=x;
4. S1 stack:x=stack[top[0]--];
S2 into the stack:x=stack[top[1]++];
5. Stacks with:top[0]+1==top[1]
Is true.
2. Simulate queues with stacks
We use two stacks to implement queue operation, but it may not achieve the effect of queue, so we need to discuss which can not achieve the effect we need.Offer 09. Implement queues with two stacksAnd that’s kind of the same idea.The operation of stack emulation queue can only be realized if the following rules are met. 1. If S1 is not full, the element is directly added to S1; 2. If S1 is full, s2empty
, the elements in s1all
Unstack merges into S2, vacates space and reenters S1.
Queue ejection rule: 1. If S2 is not empty, the elements in S2 are directly removed from the stack. 2. If S2 is empty, all elements from S1 are pushed out of the stack into S2, and then out of the stack from S2.
Full team: if S1 is full and S2 is not empty, the team cannot continue to join the team.
8. Matching parentheses
1. Parentheses
Match:Don’t match:
Use stack to realize the idea: by scanning from left to right, when the matching bracket is out of the stack; After the scan is complete, the brackets match when the stack is empty, and the brackets do not match when the stack is not empty. Matching rules:
int isMatched(char left,char right)
{
if(left=='('&&right==') ')
return 1;
else if(left=='['&&right=='] ')
return 1;
else if(left=='{'&&right=='} ')
return 1;
else
return 0;
}
Copy the code
Total code:
#include<bits/stdc++.h>
using namespace std;
#define maxSize 10
int isMatched(char left,char right)
{
if(left=='('&&right==') ')
return 1;
else if(left=='['&&right=='] ')
return 1;
else if(left=='{'&&right=='} ')
return 1;
else
return 0;
}
int isParenttheseBalanced(char exp[])
{
char s[maxSize];int top=- 1;
for(int i=0; exp[i]! ='\ 0'; ++i) {if(exp[i]=='('||exp[i]=='['||exp[i]=='{')
s[++top]=exp[i];
else{
if(top==- 1)
return 0;
char left=s[top--];
if(isMatched(left,exp[i])==0) {return 0; }}}if(top>- 1)
return 0;
return 1;
}
int main(a){
char exp[]={};
string name="{[()]}";
strcpy(exp,name.c_str());
cout<<isParenttheseBalanced(exp)<<endl;
string name1="] {} ())";
strcpy(exp,name1.c_str());
cout<<isParenttheseBalanced(exp)<<endl;
}
Copy the code
Results:
2. Calculation problems
FAQ:If the above formula doesn’t make sense, look at the following example:This is actually a very similar idea to recursion, but we’re doing it on a stack.It’s also relatively simple to implement.
int calF(int m)
{
int cum=1;
int s[maxSize],top=- 1;
while(m! =0)
{
s[++top]=m;
m/=3; // This is integer division
}
while(top! =- 1)
cum*=s[top--];
return cum;
}
Copy the code
Summary of the stack test points.