Basic C++ program using stack (just need the .cpp file)

Background

There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.

The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way.

Assume that the train arriving from the direction A has N 1000 coaches numbered in increasing order 1, 2, , N.

The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a₁, a₂, , a_n. Help him and write a program that decides whether it is possible to get the required order of coaches.

You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B.

You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.

Program Input

The input file consists of blocks of lines, each of which is a test case. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer , which is the number of coaches in the train. In each of the next lines of the block there is a permutation of 1, 2, , N . For example, if N is 5, and the permutation could be 5, 3, 2, 1, 4. Your program will take this permutation as input and determine whether you can marshal the coaches from track A an incoming order 1, 2, 3, 4, 5 to track B with an outgoing order 5, 3, 2, 1, 4 using the station, which can be treated as a stack.

The last line of the block contains just 0.

If a block starts with a zero, the program will terminate. You should use the input file named lab1in.txt (see end) to test your program; an output file named lab1out.txt (with correct output) is also provided for you to verify your program.

Input Sample

5 //start of first block

1 2 3 4 5

5 4 1 2 3

0 //end of first block

6 //start of second block

6 5 4 3 2 1

0 //end of second block

0 //end of input

Program Output

The output file contains the lines corresponding to the lines with permutations in the input file. A line of the output file contains "Yes" if it is possible to marshal the coaches in the order required on the corresponding line of the input file. Otherwise it contains "No". In addition, there is one empty line after the lines corresponding to one block of the input file. There is no line in the output file corresponding to the last "null'' block of the input file.

Output Sample

This is an output sample of the previous input sample:

Yes

No

Yes

lab1in.txt

162

10 139 138 4 28 117 63 31 48 74 11 49 118 52 128 153 130 47 17 95 110 18

70 24 112 26 64 115 141 30 87 8 46 34 80 36 13 38 39 102 61 76 120 23 156

106 116 68 85 147 59 121 78 37 53 50 54 91 101 60 94 22 107 71 123 6 67

103 145 152 75 134 73 108 25 140 77 104 127 20 81 2 154 96 151 86 135 88

89 90 58 1 93 161 29 35 97 56 79 82 124 19 7 142 21 143 100 129 109 146

111 5 98 55 45 133 43 16 148 92 113 42 65 83 125 126 114 51 3 62 144 157

150 57 40 136 137 159 162 131 119 69 44 99 158 14 33 9 149 105 15 32 41 12

155 122 132 84 66 72 160 27

1.

2 6 5 9 8 7 4 3 12 11 13 10 17 18 20 22 21 25 31 30 32 33 29 34 35 28

41 40 42 39 43 38 46 47 48 51 50 49 45 52 44 56 55 54 53 37 57 36 58 59

60 27 26 61 62 24 23 19 16 65 66 64 67 68 63 15 75 74 73 72 76 77 79 80

82 83 81 85 88 87 94 93 95 92 96 97 91 90 99 102 101 104 105 103 107

111 110 109 108 106 100 112 98 89 114 117 116 118 115 113 119 121 120

123 122 124 126 127 128 130 129 125 131 132 135 136 139 138 140 137 134

133 142 145 148 149 147 153 155 154 152 151 156 150 146 144 160 159 158

157 161 143 141 86 84 78 71 70 69 14 162

144 44 136 40 128 141 8 115 125 131 58 55 145 14 64 28 19 59 76 48 25 16

20 27 7 143 63 112 17 30 65 34 39 130 117 67 82 120 85 154 107 42 151 99

96 46 47 159 162 22 66 12 53 157 113 38 97 11 29 18 10 24 60 75 4 132 90

122 56 79 119 72 150 80 103 35 106 102 15 54 69 6 62 105 5 84 87 88 89 51

91 70 93 95 123 140 77 41 26 100 111 23 161 142 36 133 57 92 109 21 50 104

110 149 101 155 134 61 160 129 98 68 33 124 73 126 1 135 152 32 118 138

147 49 139 3 137 31 52 71 13 2 45 127 9 146 108 43 78 86 121 81 153 148 83

156 114 94 116 158 37 74

82 123 152 156 5 23 125 162 96 61 108 92 110 14 20 86 60 75 124 48 129 84

111 24 121 157 37 34 50 30 114 32 113 44 115 58 158 74 88 131 151 19 6 102

80 54 4 126 8 10 51 89 53 29 7 56 12 128 59 90 55 38 35 33 159 16 112 137

69 142 99 72 46 9 101 3 1 78 57 15 141 140 83 146 154 120 130 41 49 43 2

63 65 42 67 91 138 160 97 21 85 66 144 104 105 106 107 109 70 87 95 133 45

81 11 116 149 118 119 100 28 136 93 13 26 52 127 145 153 77 73 36 27 31

135 122 134 94 64 17 161 132 143 103 139 18 147 79 98 150 47 76 71 22 39

68 148 117 62 25 155 40

1.

39 89 4 97 21 49 8 12 154 29 27 121 14 79 91 94 158 19 109 132 124 23

84 16 26 157 73 81 28 5 17 47 86 35 80 146 126 71 40 133 90 61 99 111

46 134 48 95 33 51 20 112 156 45 102 57 41 147 60 106 100 161 64 65 66

9 11 74 110 36 15 115 69 63 152 3 118 2 145 30 82 155 58 122 135 120 88

31 98 34 44 150 142 148 96 72 125 92 54 101 128 59 119 105 139 25 78 24

70 153 53 162 62 160 104 68 56 123 18 103 114 87 6 52 136 127 141 32 38

131 117 10 138 140 159 137 13 37 108 116 67 143 130 107 76 113 75 149

85 43 50 22 93 83 55 129 144 7 77 42 151

1.

2 4 5 3 8 7 6 9 10 11 13 12 16 15 17 21 22 20 19 18 14 23 24 25 26 28

27 29 36 37 35 38 43 42 41 40 39 34 33 48 49 50 51 52 53 47 46 55 54 45

56 44 58 57 32 31 60 61 62 59 64 65 69 68 72 71 74 73 70 67 75 66 63 30

77 78 79 76 82 81 84 83 85 80 90 91 89 92 94 93 88 95 87 86 96 97 101

102 100 103 105 104 99 98 109 112 111 113 114 110 120 119 125 124 123

126 122 121 127 118 129 131 130 136 135 137 139 138 140 134 133 142 147

146 148 152 153 151 156 157 158 160 159 161 155 154 150 149 145 144 143

141 132 128 117 116 115 108 107 106 162

2.

3 1 6 5 7 8 9 14 17 16 19 18 26 25 24 27 29 28 23 30 31 22 34 37 38 39

40 36 42 41 43 44 45 35 46 33 32 47 21 20 15 13 12 48 11 50 52 53 51 49

10 4 55 56 54 58 60 61 59 62 57 64 63 65 66 69 70 71 68 67 76 77 75 79

82 81 80 78 83 74 84 73 85 87 86 88 72 89 90 91 93 92 98 97 101 102 100

99 96 103 104 111 112 113 110 109 108 114 117 122 125 124 127 131 132

130 137 136 138 140 143 145 152 151 150 149 148 153 147 154 146 155 144

142 157 156 141 139 135 159 158 161 160 134 133 129 128 126 123 121 120

119 118 116 115 107 106 105 95 94 162

0

0

lab1out.txt

No Yes No No No Yes Yes

Hint

Key points to understand/solve the problem:

The train station can be regarded as a stack.

One can push a coach from track A into the stack; when the coach is popped out of the stack, it gets into track B, and a coach in the station can never go back to track A.

Taking a train with 5 coaches as an example.

Coaches in track A is always in strictly increasing order, i.e., 1, 2, 3, 4, 5

The train chief tries to marshal the coaches into track B via a sequence of push and pop operations.

Each test case in the input file is asking a question: is it possible to marshal the the coaches into track B such that the coach order matches the test case?

For instance, if the test case is "1, 2, 3, 4, 5", then we can perform the following sequence of operations

The final coach order in track B matches "1,2,3,4,5" in the test case, so program outputs "YES".

Now use a similar way to validate that why test case "5, 4, 1, 2, 3" will NOT work.

Now you should be able to handle larger test cases as the ones in the input file provided by the instructor.

5, 4, 3, 2,1 1, 2 3, 45 Station