Stack problem in pascal language.

Don't copy Pascal upstairs if he doesn't understand! ! !

This is blasphemy.

I also have a stack of PPT handouts. Please send me your email address, thank you. I will send the attachment to the mailbox.

Concept and operation of 1 stack

Definition of stack: stack is a special table, which can only be inserted and deleted in the header. Therefore, the header has a special meaning for the stack, which is called the top of the stack. Therefore, the footer is called the bottom of the stack. A stack without any elements is called an empty stack.

Logical structure of stack: suppose the elements in a stack S are an, an- 1, ..., a 1, then A 1 is called the bottom element of the stack, and an is the top element of the stack. The elements in the stack are A 1, A2, ..., An- 1, An. At any time, the element that leaves the stack is the top element of the stack. In other words, the stack is modified according to the principle of LIFO, as shown in figure 1. Therefore, stack is also called LIFO table, LIFO table for short. So as long as the problem satisfies LIFO principle, the stack can be used.

Stack operation: As an abstract data type, the commonly used stack operations are:

Operational meaning

Make s an empty stack.

GetTop(S) This is a function whose value is the top element in S.

Pop(S) deletes the top element from stack S, which is called stack throw for short.

Push(S, x) inserts element X at the top of S stack, which simply means putting element X on the stack.

This is a function. When s is an empty stack, the function value is true, otherwise the function value is false.

Storage and implementation of 2 stack

Array implementation of stack: Because the stack is a special table, we can use arrays to implement the stack. Considering the particularity of stack operation, when we use array elements [1...maxlength] to represent a stack, we fix the bottom of the stack at the bottom of the array, that is, elements[ 1] are the earliest elements put into the stack, so that the stack can be extended to the top of the array (in the direction of increasing subscripts). At the same time, we use a cursor top to represent the unit where the current stack top element is located. When top=0, it means that the stack is empty. Generally speaking, the order of elements [top], elements [top- 1], ... and elements [1] form a stack. This structure is shown in Figure 2.

Figure 2

Using the above structure, we can formally define the stack type TStack as follows:

type

TStack = record

Top: integer;

Element: array [1 ... maximum length];

End;

In this representation, the five basic operations of the stack can be realized as follows.

Process instack (var s: tstack);

begin

s . top:= 0；

End;

Function empty (var s: stack): Boolean;

begin

return(s . top = 0)；

End;

Var S:TStack: telemetry;

begin

If it is empty, an error occurs ("Stack is empty." )

else return(s . element[s . top])；

End;

Process Pop(var S:t stack)；);

begin

If it is empty, an error occurs ("Stack is empty." )

else dec(s . top)； {S.top minus 1}

End;

Process push (var S:t stack；; X: telemetry; );

begin

If S.top=maxlength, an error ('stack full') occurs.

Otherwise start.

Inc(s . top)； {S.top has added 1}

s . elements[s . top]:= x；

End;

The complexity of each of the above operations is O( 1).

In some cases, it may be necessary to use multiple stacks of the same type at the same time. In order to make each stack not overflow when the algorithm runs, a large stack space should be set at the top of each stack. Doing so often leads to a waste of space. In fact, in the process of algorithm running, each stack is generally not full at the same time, and it is likely that some are full and some are empty. Therefore, if we let multiple stacks share the same array and dynamically adjust each other, it will improve the utilization of space and reduce the possibility of stack overflow. Suppose we let two stacks in the program share an array S [1...n]. Taking advantage of the constant position of the stack bottom, we can set the stack bottom of two stacks at both ends of the array S, and then extend to the middle respectively, as shown in Figure 3. The initial values of the two S stacks are 0 and n+ 1 respectively. Overflow occurs only when the tops of two stacks meet. Because two stacks can complement each other, the maximum space actually available for each stack is usually greater than n/2.

Application of 3 stack

1. expression evaluation

Question: Can you design an algorithm and write a program to let the computer scan the following expressions and print out their values?

# 3 * ( 4 + 8 ) / 2 -5 #

Note: Set # as an expression to mark the start and end of scanning.

Hint algorithm: Set two stacks, one is operand stack, which is used to store operands, such as 3, 4 and 8, and the other is operator stack, which is used to store operators.

First, put the flag "#" at the bottom of the operator stack.

Then scan the stack in turn according to the principle of last in first out:

(1) When encountering an operand, enter the operand stack;

(2) When you encounter an operator, you need to compare the priority of this operator with the priority of the top-level operator.

If it is higher than the top element of the stack, it enters the stack and continues to scan the next symbol.

Otherwise, the top element of the operator stack is returned to form the operation code Q, and the top element of the operand stack is returned twice to form two operands A and B, so that the computer can perform an operation on the operand and the operation code once, namely aQb, and store the operation result in the operand stack. ...

Simulate the process of computer processing arithmetic expressions. Input an arithmetic expression string from the keyboard (only+,-,×, ÷ operator and brackets are allowed) and output the value of the arithmetic expression. Make the input expression string legal.

Additional source program:

Program EXSJ _1;

constant

max = 100；

defined variable

Number: integer of array [0..max];

Symbol: array [1... max]； of char];

S, t: string;

I, p, j, code: integer;

Program push; {Operator Stacking Operation}

begin

Inc(p)； Symbol [p]: = s [I];

End;

The program pops up; {Pop up the top element of the operator stack, take out the element of the operand stack, and complete the corresponding operation}

begin

dec(p)；

Case symbol of [p+ 1]

+':inc (No.[p],No. [P+1]);

-':dec (number [p], number [p+1]);

*:number[p]:= number[p]* number[p+ 1]；

/':number[p]:= number[p]div number[p+ 1]；

End;

Functions can be Boolean; {Judge the operator's priority level and establish the marking function}

begin

Can: = true;

If (s[i] in ['+','-']) and (symbol [p] <; & gt (') and then exit;

If (s[i] in ['*',/']) and ['*',/']) and then exit;

Can: = false;

End;

begin

write(' String:')； readln(s)； s:= '('+s+')'； I:= 1； p:= 0；

And I < = length do.

begin

While s[I]= '(' do {left parenthesis processing]

begin

Push; Inc (1);

End;

j:= I；

Repeat {Extract data to operand stack}

Inc (1);

Until (s [I] <; 0') or (s [I] >' 9');

t:=copy(s，j，I-j)； Val(t, number [p], code);

repeat

If s[i]=')', then {closed bracket processing}

begin

While symbol [p] < & gt(do pop

dec(p)； Number [p]:= number [p+1];

end

other

Start {Operate the operator stack entry or stack exit according to the flag function value}

You can do pop instead.

Push;

End;

Inc (1);

Until (I> length (s)) or (s [I-1] < & gt')');

End;

write('Result= '，number[0])；

readln

End.

2. knapsack problem

Question: Suppose there are n items with a mass distribution of w 1, w2, ..., wn and a backpack with a maximum total mass of t, can you select several items from these n items and put them into the backpack so that the total mass of the selected items is exactly equal to the maximum mass that the backpack can carry, that is, Wi1+WI2+...+WIK = T.

Algorithm idea: firstly, arrange n items in a row and select them in turn; If the total mass of the items in the backpack does not exceed the maximum loading mass after loading an item in the backpack, it is loaded (stacked); Otherwise, give up the choice of this item and choose the next item for testing until the sum of the loaded items is exactly the maximum reprint quality of the backpack. At this time, we call our backpacks full.

If the backpack with several items is not full and there are no other items that can be selected into the backpack, it means that there are unqualified items in the backpack. You need to take out the last loaded item from the backpack (return to the stack), and then select from the unloaded items, and repeat this process until the backpack is full (solution) or there are no items to select (solution).

Specific implementation: let the weights of the array be [1...n] and stack[ 1, N] to store the weight and item number of the items that have been loaded into the stack, respectively, and MaxW represents the maximum loading capacity of the backpack. Every time an item is stacked, the mass of the item is subtracted from MaxW, and I is the serial number of the item to be selected. if MaxW-weight[I]>； =0, this option is optional; if maxw-weight[I]； N, you need to return to the stack. If the stack is empty at this time, there is no solution.

Reference function realized by Pascal;

Function knapstack(n, MaxW, weight);

begin

top:= 0； I:= 1； {i is the serial number of the item to be selected}

while(MaxW & gt； 0) and (i< do

begin

if(MaxW-weight[I]& gt； =0) and (I < = n) Then

begin top:= top+ 1； stack[top]:= I； MaxW = MaxW-weight[I]end；

{The first item is put into the backpack}

Returns (true) if MaxW=0.

Otherwise start.

If (i=n) and (top>0) and then {there are inappropriate items in the backpack}