CHP 5:
https://www.youtube.com/watch?v=ns-r91557ds
? (stack):
(LIFO:Last-In First-Out):. D C B C B C B C B
(element) C (top) B (bottom)
(DT) : n element : create() ::=. is_empty(s) ::=. is_full(s) ::=. push(s, e) ::= e. pop(s) ::=. peek(s) ::=.
push(): pop():
push(): pop():
push(): pop():
push(): pop(): push()
push(): pop(): push()
push(): pop(): push()
push(): pop(): push()
push(): pop(): push() push(b)
push(): pop(): push() push(b)
push(): pop(): push() push(b) B
push(): pop(): push() push(b) B
push(): pop(): push() push(b) B
push(): pop(): push() push(b) B
push(): pop(): push() push(b) B B
push(): pop(): push() push(b) push(c) B B
push(): pop(): push() push(b) push(c) B C B
push(): pop(): push() push(b) push(c) B C B
push(): pop(): push() push(b) push(c) B C B
push(): pop(): push() push(b) push(c) C pop() B B
push(): pop(): push() push(b) push(c) C pop() B B
push(): pop(): push() push(b) push(c) C pop() B B B
is_empty(s): is_full(s): create(): peek(s): ( )pop.
(undo) 1 20 100 150 200 int main() { int i=3; sub1(i);... int sub1(int a) { int j=5; sub2(j);... void sub2(int b) {... main PC=1 sub1 PC=20 a=3 main i=3 sub2 PC=150 b=5 sub1 PC=20 a=3 j=5 main i=3 sub1 PC=20 a=3 j=5 main i=3 main i=3
1 stack[ ] top stack[0], stack[top] top -1 4 4 4 top 3 3 3 2 2 top 2 1 1 1 0-1 top 0-1 0-1
is_empty, is_full is_empty(s) is_full(s) if top = -1 then return TRUE else return FLSE if top = (MX_STCK_SIZE-1) then return TRUE else return FLSE 4 4 top 3 3 2 2 1 1 0-1 top 0-1
push push(s, x) if is_full(s) then error "overflow" else top top+1 stack[top] x 4 3 2 1 0 top 4 3 2 1 0 top
pop pop(s, x) if is_empty(s) then error "underflow" else e stack[top] top top-1 return e 4 3 2 1 0 top 4 3 2 1 0 top
C typedef int element; typedef struct { element stack[mx_stck_size]; int top; StackType; element // void init(stacktype *s) { s->top = -1; // int is_empty(stacktype *s) { return (s->top == -1); // int is_full(stacktype *s) { return (s->top == (MX_STCK_SIZE-1));
// void push(stacktype *s, element item) { if( is_full(s) ) { fprintf(stderr," \n"); return; else s->stack[++(s->top)] = item; // element pop(stacktype *s) { if( is_empty(s) ) { fprintf(stderr, " \n"); exit(1); else return s->stack[(s->top)--]; // element peek(stacktype *s) { if( is_empty(s) ) { fprintf(stderr, " \n"); exit(1); else return s->stack[s->top];
push
Lab ivis.kr
(linked stack): : :. 4 3 9 top 2 1 9 7 top 7 0 3 3 NULL
typedef int element; typedef struct StackNode { element item; struct StackNode *link; StackeNode; typedef struct { StackNode *top; LinkedStackType; 9 top 7 3 NULL
push // void push(linkedstacktype *s, element item) top { StackNode *temp=(stacknode *)malloc(sizeof(stacknode)); if( temp == NULL (2) ){ (1) fprintf(stderr, " \n"); return; temp D else{ temp->item = item; temp->link = s->top; s->top = temp; C B NULL
// pop element pop(linkedstacktype *s) { if( is_empty(s) ) { else{ fprintf(stderr, " \n"); exit(1); StackNode *temp=s->top; int item = temp->item; s->top = s->top->link; free(temp); return item; top C B NULL temp
: ( [, ] ), ( {, ), ( (, ) ) ` 1.. 2.. 3.. (a(b) a(b)c) a{b(c[d]ef)
if( ( i==0 ) && (j==0 ) ( ) ( ( ( ( ( ( ( ( ( ( { [ (i+1 ) ]=0; ( [ { { [ { ( [ [ { { {
, top., 1 2 3. 1 0( ), 1( ).
check_matching(expr) while ( expr ) ch expr switch(ch) case '(': case '[': case '{': ch break case ')': case ']': case ']': if ( ) then else open_ch if (ch open_ch ) then break if( ) then
// int check_matching(char *in) { StackType s; char ch, open_ch; int i, n = strlen(in); init(&s); for (i = 0; i < n; i++) { ch = in[i]; switch(ch){ case '(': case '[': push(&s, ch); break; case '{':
case ')': case ']': case '': if(is_empty(&s)) return FLSE; else { open_ch = pop(&s); if ((open_ch == '(' && ch!= ')') (open_ch == '[' && ch!= ']') (open_ch == '{' && ch!= '')) { return FLSE; break; if(!is_empty(&s)) return FLSE; return TRUE; int main() { if( check_matching("{ [(i+1)]=0; ") == TRUE ) printf(" \n"); else printf(" \n");
: (prefix), (infix), (postfix) 2+3*4 +2*34 234*+ a*b+5 +5*ab ab*5+ (1+2)+7 +7+12 12+7+ -> -> 2+3*4 -> 234*+ -> 14
( ) 82/3-32*+ [0] [1] [2] [3] [4] [5] [6] 8 8 2 8 2 / 4 3 4 3-1 3 1 3 2 1 3 2 * 1 6 + 7
0 1 2 3 8 8 2 / 3-0 1 2 3 8 8 2 / 3-2 0 1 2 3 4 8 2 / 3 - -> -> -> 8/2=4 0 1 2 3 4 8 2 / 3-0 1 2 3 1 8 2 / 3-0 1 2 3 1 8 2 / 3-3 -> -> 4-1=1 -> =1
s. for in do if ( ) push(s, item) if ( op ) then second pop(s) first pop(s) result first op second // op +-*/ push(s, result) final_result pop(s);
// eval(char exp[]) { int op1, op2, value, i=0; int len = strlen(exp); char ch; StackType s; init(&s); for( i=0; i<len; i++){ ch = exp[i]; if( ch!= '+' && ch!= '-' && ch!= '*' && ch!= '/' ){ value = ch - '0'; // push(&s, value); else{ // op2 = pop(&s); op1 = pop(&s); switch(ch){ // case '+': push(&s,op1+op2); break; case '-': push(&s,op1-op2); break; case '*': push(&s,op1*op2); break; case '/': push(&s,op1/op2); break; return pop(&s);
( ) ->. 2+3*4 -> 234*+ ->
( a + b ) * c (
( a + b ) * c a (
( a + b ) * c + a (
( a + b ) * c + a b (
( a + b ) * c a b +
( a + b ) * c a b + *
( a + b ) * c a b + c *
( a + b ) * c a b + c *
infix_to_postfix(exp) s while (exp ) ch switch (ch) case : while ( peek(s) ch ) do e pop(s) e push(s, ch); break; case : push(s, ch); break; case : e pop(s); while( e ) do e e pop(s) break; case : ch break; while( not is_empty(s) ) do e pop(s) e
// -> void infix_to_postfix(char exp[]) { int i = 0; char ch, top_op; int len = strlen(exp); StackType s; init(&s); for (i = 0; i<len; i++) { ch = exp[i]; // // switch (ch) { case '+': case '-': case '*': case '/': // // while (!is_empty(&s) && (prec(ch) <= prec(peek(&s)))) printf("%c", pop(&s)); push(&s, ch); break; case '(': // push(&s, ch); break;
case ')': // top_op = pop(&s); // while( top_op!= '(' ){ printf("%c", top_op); top_op = pop(&s); break; default: // printf("%c", ch); break; while(!is_empty(&s) ) // printf("%c", pop(&s)); // main() { infix_to_postfix("(2+3)*4+9");
. 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 m 0 1 0 1 1 0 1 0 0 0 0 1 0 x 1 1 1 1 1 1 1 1 1 1
s x, while( ) do ; if(,,, ) then push if( is_empty(s) ) then else ;
#define MX_STCK_SIZE 100 #define MZE_SIZE 6 typedef struct StackObjectRec { short r; short c; StackObject; StackObject stack[mx_stck_size]; int top = -1; StackObject here={1,0, entry={1,0; char maze[mze_size][mze_size] = { {'1', '1', '1', '1', '1', '1', ; {'e', '0', '1', '0', '0', '1', {'1', '0', '0', '0', '1', '1', {'1', '0', '1', '0', '1', '1', {'1', '0', '1', '0', '0', 'x', {'1', '1', '1', '1', '1', '1',
void pushloc(int r, int c) { if( r < 0 c < 0 ) return; if( maze[r][c]!= '1' && maze[r][c]!= '.' ){ StackObject tmp; tmp.r = r; tmp.c = c; push(tmp); void printmaze(char m[mze_size][mze_size]) {
void printstack() { int i; for(i=5;i>top;i--) printf(" \n"); for(i=top;i>=0;i--) printf(" (%01d,%01d) \n", stack[i].r, stack[i].c); printf("-------\n");
void main() { int r,c; here = entry; printmaze(maze); printstack(); while ( maze[here.r][here.c]!='x' ){ printmaze(maze); r = here.r; c = here.c; maze[r][c] = '.'; pushloc(r-1,c); pushloc(r+1,c); pushloc(r,c-1); pushloc(r,c+1);
printstack(); if( isempty() ){ printf(" \n"); printf(" \n"); return; else here = pop(); printmaze(maze); printstack(); getch();
Last In First Out,,
#6 5 Exercises 2-16, : 5 2