[Data Structure] Judging the legitimacy of the outlet order

A brief description of the problem

Given a stacking order, and then specify a stacking order, the legality of the stacking order is judged by the program.

The idea is as follows:

Define an empty stack sc

put the first element in str1 onto the stack first, and then make it through the loop str1 moves back.

1. If the current stack is empty and the push sequence is not empty, the push sequence str1 is moved backward, and sp is pushed into the stack.

2. If the top element of the stack is not equal to the pop sequence and the pop sequence is not empty, the pop sequence str1 is moved backward, and sp is popped into the stack.

3. If the top element of the stack is equal to the pop sequence, sp pops from the stack, and the pop sequence str2 moves back.

After the loop comparison, if the stack is empty, the pop sequence is legal.

Take the stack 12345 and pop 45312 as an example, now put 123 into sc, find the element in str1 that is the same as the top element of str2, sc pop out of the stack, after str2 When str2 points to 1, sc points to 1, which is not equal, but str1 is still moved backward. If sc is not empty, the stacking order is illegal.

The simple code is as follows;

mystack

mystack

span>

#include #include#include#include using namespace std;class IsTrueSack{public: IsTrueSack() :_str1(NULL) ,_str2(NULL) {} ~IsTrueSack() {if (_str1!=NULL) {delete[] _str1;} if (_str2!=NULL) {delete[] _str2;} }public: bool IsTrue(const char *push_seq, const char *pop_seq)//Judging whether the pop order is correct {if (NULL == push_seq || NULL == pop_seq)//If it is If empty, return false directly {cout<<"not the correct order"<sc;//Reconstruct a new stack s to store the push_seq stack order while (*push_seq) {if (0 == sc.size() || sc.top() != *pop_seq)//Judging whether the length of sc is empty {sc.push(*push_seq++);} else//If the above description is not met, some elements have been popped out of the stack, sc After popping out of the stack, pop_seq moves one step back and continues the previous step to determine, looping {sc.pop(); ++pop_seq;}} while (sc.size()) {if (sc.top() != *pop_seq++ ) {cout<<"is not the correct order"<
 Test code

#include "MyStack.h"#include int main(){ test1(); test2(); test3(); test4(); system(" pause"); return 0;}
 Run result: