3. Applications Balancing Symbols Check if parenthesis(), brackets[], and braces() are balanced Algorithm i Make an empty stack S TONDO(N) while(read in a character c)t where n is the length if(c is an opening symbol) of the expression Push(, S) This is an else if (c is a closing symbol) if(s is empty)I ERROR; exit; y on-line algorithm else/stack is okay if(Top(s)doesnt match c)I ERROR, exit; 1 else Pop(s); 1 / end else-stack is okay * 3/end else-if-closing symbol * 3/end while-loop*/ if(s is not empty) ERROR
3. Applications Balancing Symbols Check if parenthesis ( ), brackets [ ], and braces { } are balanced. Algorithm { Make an empty stack S; while (read in a character c) { if (c is an opening symbol) Push(c, S); else if (c is a closing symbol) { if (S is empty) { ERROR; exit; } else { /* stack is okay */ if (Top(S) doesn’t match c) { ERROR, exit; } else Pop(S); } /* end else-stack is okay */ } /* end else-if-closing symbol */ } /* end while-loop */ if (S is not empty) ERROR; } T( N ) = O ( N ) where N is the length of the expression. This is an on-line algorithm
a digital conversion n=(n div dxd+N mod d Example:(1348)10=(2504)8, the Computing process is as follows n ndiv 8 Nmod 1348168 4 16821 21 2 2 0 052
N = (N div d)×d + N mod d Example：（1348)10 = (2504)8 ，the Computing process is as follows： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 Output order Order of computation digital conversion
void conversion oi nitStack(s); scanf(%od" N; while(ni Push(s,n%8); N=N/8; while(stackEmpty())i Pop(s,e) printf (%d",e )i }∥ conversion
void conversion () { InitStack(S); scanf ("%d",N); while (N) { Push(S, N % 8); N = N/8; } while (!StackEmpty(S)) { Pop(S,e); printf ( "%d", e ); } } // conversion
Line editor when users input a line of characters, line editor allows to input wrong characters, and it can correct errors timely. Create a input buffer to store a line of characters of users input, and then store to data storage area line by line. Suppose #' to backspace and'to denote cancelling a line of input Assume that editor accept two lines of characters from the terminal whli##ilr#e( s#*s) outcha @putchar(s=#++); The editor should store while(s) putchar(s++);
when users input a line of characters, line editor allows to input wrong characters, and it can correct errors timely. Create a input buffer to store a line of characters of users input, and then store to data storage area line by line. Suppose ‘#’ to backspace and ‘@’ to denote cancelling a line of input. Assume that editor accept two lines of characters from the terminal ： whli##ilr#e（s#*s) outcha@putchar(*s=#++); The editor should store： while (*s) putchar(*s++); Line editor
Void Lineeditoi Initstack(s); ch=getchar; while(ch!=EOF){/EOF为全文结束符 while(ch !- EoF & ch !=n)i switch(ch)i case #: Pop(s, c); break; case ' @ ClearStack(S); break; ∥重置S为空栈 default: Push(s, ch); break; ch= getchar;∥从终端接收下一个字符
Void LineEdit(){ InitStack(s); ch=getchar(); while (ch != EOF) { //EOF为全文结束符 while (ch != EOF && ch != '\n') { switch (ch) { case '#' : Pop(S, c); break; case '@': ClearStack(S); break; // 重置S为空栈 default : Push(S, ch); break; } ch = getchar(); // 从终端接收下一个字符 }