---------------- DATA STRUCTURES USING C ---------------- 03CHAPTER 1
? (stack): (LIFO:Last-In First-Out) 2
: top : ( index -1 ),,, 3
: ( ) ( ) -> ->. ->.... 4
Stack ADT : (LIFO) : init():. is_empty(): TRUE FALSE. is_full(): TRUE FALSE. size():. push(x): x. pop():. peek():. 5
(push), (pop) is_empty(): is_full(): peek(s): ( ) pop. 6
Undo 7
(Undo) - LAB ^+Z Comm+Z 8
1 stack[ ] top: stack[0] stack[top]: top -1 9
Push C 4 4 3 3 2 2 C top 1 B top 1 B 0 A 0 A push(x) if is_full(s) then error "overflow" else top top+1 data[top] x 10
Pop 4 4 3 3 2 C top 2 1 B 1 B top 0 A 0 A pop() if is_empty() then error "underflow" else e data[top] top top-1 return e 11
data[] top! typedef int Element; Element data[max_stack_size]; int top; int is_empty() { if( top == -1 ) return 1; else return 0; } void init_stack() { top = -1; } int size() { return top+1; } int is_empty() { return (top == -1); } int is_full() { return (top == MAX_STACK_SIZE-1); } 12
void push ( Element e ) { if( is_full() ) error (" "); data[++top] = e; } Element pop ( ) { if( is_empty() ) error (" "); return data[top--]; } Element peek ( ) { if( is_empty() ) error (" "); return data[top]; } void print_stack(char msg[]) { int i; printf("%s[%2d]= ", msg, size()) ; for (i=0 ; i<size() ; i++ ) printf("%2d ", data[i]); printf("\n"); } 13
void main() { int i; init_stack(); for( i=1 ; i<10 ; i++ ) push( i ); print_stack(" push 9 "); printf("\tpop() --> %d\n", pop()); printf("\tpop() --> %d\n", pop()); printf("\tpop() --> %d\n", pop()); print_stack(" pop 3 "); } 14
Lab ex3.1 15
Element typedef struct Student_t { int id; char name[32]; char dept[32]; } Student; typedef Student Element; void print_stack(char msg[]) { int i; printf("%s[%2d]= ", msg, size()) ; for (i=0 ; i<size() ; i++ ) printf("\n\t%-15d %-10s %-20s", data[i].id, data[i].name, data[i].dept); printf("\n"); } 16
Student get_student(int id, char* name, char* dept) { Student s; s.id = id; strcpy(s.name, name); strcpy(s.dept, dept); return s; } void main() { init_stack( ); push( get_student(2015130007, " ", " ") ); push( get_student(2015130100, " ", " ") ); push( get_student(2015130135, " ", " ") ); push( get_student(2015130135, " ", " ") ); print_stack(" 4 "); pop( ); print_stack(" 1 "); } 17
Lab ex3.2 18
19
20
: : ( [, ] ), ( {, } ), ( (, ) )... (a(b) a(b)c) a{b(c[d]e}f) 21
23
, top., 1 2 3. 1 0( ), 1( ). 24
check_matching(expr) while ( expr ) ch expr switch(ch) case '(': case '[': case '{': ch break case ')': case ']': case ']': if ( ) then else open_ch break if( ) then if (ch open_ch ) then 25
void main() { char expr[4][80] = { "{A[(i+1)]=0;}", "if((i==0) && (j==0)", "A[(i+1])=0;", "A[i] =f)(;" }; int err, i; for( i=0 ; i<4 ; i++ ) { err = check_matching(expr[i]); if( err == 0 ) printf(" : %s\n", expr[i]); else printf(" : %s ( %d )\n", expr[i], err); } } 26
Lab - ex3.3 27
28
: (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 29
Calc_postfix (expr) ; for in expr do if ( ) s.push(item); if ( op ) then second pop(); first pop(); result pop(); temp first op second; // op +-*/ push(temp); 30
31
double calc_postfix( char expr[] ) {... init_stack( ); while( expr[i]!= '\0' ) { c = expr[i++]; if (c>='0' && c<='9') { val = c - '0'; push( val ); } else if( c=='+' c=='-' c=='*' c=='/' ){... switch( c ) { case '+': push( val1 + val2); break;... } void main() { char expr[2][80] = { "8 2 / 3-3 2 * +", "1 2 / 4 * 1 4 / *" }; printf(" : %s = %lf\n", expr[0], calc_postfix(expr[0])); printf(" : %s = %lf\n", expr[1], calc_postfix(expr[1])); } 32
: ( ) 2+3*4 -> 234*+ 33
! 34
35
Infix_to_postfix(expr). while (expr ) term ; switch (term) case : term ; break; case : push(term); break; case : e pop(); while( e ) do e ; e pop(); break; case : while ( peek() term ) do e pop(); e ; push(term); break; while( not is_empty() ) do e pop(); e ; 36
static int precedence( char op ) { switch (op) { case '(' : case ')' : return 0; case '+' : case '-' : return 1; case '*' : case '/' : return 2; } return -1; } void infix_to_postfix( char expr[] ) {...} void main() { char expr[2][80] = { "8/2-3+(3*2)", "1/2* 4 * (1/4)" }; printf(" : %s ==> :", expr[0]); infix_to_postfix(expr[0]); printf(" : %s ==> :", expr[1]); infix_to_postfix(expr[1]); } 37
38