Chapter - III

Applications of Stacks

Syllabus
• Infix to Postfix Expression Conversion

• Postfix Expression Evaluation

• Parenthesis Balance

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 1 of 6

 Module-II Sample Programs

1 Infix to Postfix Expression Conversion

1 # include < stdio .h >
2 # include < string .h >
3

4 int F ( char ) ;
5 int G ( char ) ;
6 void infix_postfix ( char [] , char []) ;
7
8 void main ()
9 {
10 char infix [20];
11 char postfix [20];
12
13 printf ( " \ nEnter a valid infix expression > " ) ;
14 scanf ( " % s " , infix ) ;
15

16 infix_postfix ( infix , postfix ) ;

17
18 printf ( " \ nThe postfix expression is > " ) ;
19 printf ( " % s \ n " , postfix ) ;
20 }
21

22 int F ( char symbol )

23 {
24 switch ( symbol )
25 {
26 case ’+ ’:
27 case ’ - ’:
28 return 2;
29
30 case ’* ’:
31 case ’/ ’:
32 return 4;
33

34 case ’^ ’:
35 case ’$ ’:
36 return 5;
37
38 case ’( ’:
39 return 0;
40
41 case ’# ’:
42 return -1;
43
44 default :
45 return 8;
46 }
47 }
48
49 int G ( char symbol )
50 {
51 switch ( symbol )
52 {
53 case ’+ ’:
54 case ’ - ’:
55 return 1;
56
57 case ’* ’:
58 case ’/ ’:

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 2 of 6

 Module-II Sample Programs

59 return 3;
60
61 case ’^ ’:
62 case ’$ ’:
63 return 6;
64
65 case ’( ’:
66 return 9;
67
68 case ’) ’:
69 return 0;
70
71 default :
72 return 7;
73 }
74 }
75

76 void infix_postfix ( char infix [] , char postfix [])

77 {
78 int top ; /* points to top of the stack */
79 int j ; /* Index for postfix expression */
80 int i ; /* Index to access infix expression */
81

82 char s [30]; /* Acts as storage for stack elements */

83 char symbol ; /* Holds scanned char from infix expression */
84
85 top = -1; /* Stack is empty */
86 s [++ top ] = ’# ’; /* Initialize stack to # */
87 j = 0; /* Output is empty . So , j = 0 */
88
89 for ( i = 0; i < strlen ( infix ) ; i ++)
90 {
91 symbol = infix [ i ]; /* Scan the next symbol */
92
93 while ( F ( s [ top ]) > G ( symbol ) ) /* if stack precedence is greater */
94 postfix [ j ++] = s [ top - -]; /* Pop and place into postfix */
95 if ( F ( s [ top ]) != G ( symbol ) )
96 s [++ top ] = symbol ; /* push the input symbol */
97 else
98 top - -; /* discard ’( ’ from stack */
99 }
100
101 while ( s [ top ] != ’# ’)
102 postfix [ j ++] = s [ top - -]; /* pop and place in postfix */
103
104 postfix [ j ] = ’ \0 ’; /* NULL terminate */
105 }

2 Postfix Expression Evaluation

1 # include < stdio .h >
2 # include < math .h >
3 # include < string .h >
4
5 /* Function to evaluate */
6 double compute ( char symbol , double op1 , double op2 )
7 {
8 switch ( symbol )
9 {
10 case ’+ ’:

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 3 of 6

 Module-II Sample Programs

11 return op1 + op2 ; /* Perform addition operation */

12
13 case ’ - ’:
14 return op1 - op2 ; /* Perform subtraction operation */
15

16 case ’* ’:
17 return op1 * op2 ; /* Multiply two operands */
18
19 case ’/ ’:
20 return op1 / op2 ; /* Perform division */
21

22 case ’$ ’:
23 case ’^ ’:
24 return pow ( op1 , op2 ) ; /* Compute power */
25 }
26 }
27

28 void main ()
29 {
30 double s [20]; /* Place for stack elements */
31 double res ; /* Holds the result of partial or final result */
32 double op1 ; /* First operand */
33 double op2 ; /* Second operand */
34 int top ; /* Points to the topmost element */
35 int i ; /* Index to obtain each symbol from the postfix */
36 char postfix [20]; /* Valid input expression */
37 char symbol ; /* Scanned symbol of postfix */
38
39 printf ( " Enter the postfix expression \ n " ) ;
40 scanf ( " % s " , postfix ) ;
41
42 top = -1; /* Stack is empty */
43
44 for ( i = 0; i < strlen ( postfix ) ; i ++)
45 {
46 symbol = postfix [ i ]; /* Obtain the next character */
47
48 if ( isdigit ( symbol ) ) /* If operand insert into the stack */
49 s [++ top ] = symbol - ’0 ’;
50 else
51 {
52 op2 = s [ top - -]; /* Obtain second operand from stack */
53 op1 = s [ top - -]; /* Obtain first operand from stack */
54
55 res = compute ( symbol , op1 , op2 ) ; /* Perform the specified operation */
56
57 s [++ top ] = res ; /* Push the partial result on the stack */
58 }
59 }
60
61 res = s [ top - -]; /* Obtain result from the stack */
62
63 printf ( " The result is % f \ n " , res ) ;
64 }

3 Parenthesis Balance
1 # include < stdio .h >
2 # include < string .h >
3 # include < stdlib .h >

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 4 of 6

 Module-II Sample Programs

4
5 # define MAX 30
6
7 int top = -1;
8 int stack [ MAX ];
9
10 void push ( char ) ;
11 char pop () ;
12 int match ( char a , char b ) ;
13 int check ( char []) ;
14

15 int main ()
16 {
17 char exp [ MAX ];
18 int valid ;
19 printf ( " Enter an algebraic expression : " ) ;
20 scanf ( " % s " , exp ) ;
21
22 valid = check ( exp ) ;
23
24 if ( valid ==1)
25 printf ( " Valid expression \ n " ) ;
26 else
27 printf ( " Invalid expression \ n " ) ;
28
29 return 0;
30 }
31
32 int check ( char exp [] )
33 {
34 int i ;
35 char temp ;
36
37 for ( i =0; i < strlen ( exp ) ; i ++)
38 {
39 if ( exp [ i ]== ’( ’ || exp [ i ]== ’{ ’ || exp [ i ]== ’[ ’)
40 push ( exp [ i ]) ;
41
42 if ( exp [ i ]== ’) ’ || exp [ i ]== ’} ’ || exp [ i ]== ’] ’)
43 if ( top == -1) /* stack empty */
44 {
45 printf ( " Right parentheses are more than left
parentheses \ n " ) ;
46 return 0;
47 }
48 else
49 {
50 temp = pop () ;
51
52 if (! match ( temp , exp [ i ]) )
53 {
54 printf ( " Mismatched parentheses are :
");
55 printf ( " % c and % c \ n " , temp , exp [ i ]) ;
56 return 0;
57 }
58 }
59 }
60

61 if ( top == -1) /* stack empty */

62 {

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 5 of 6

 Module-II Sample Programs

63 printf ( " Balanced Parentheses \ n " ) ;

64 return 1;
65 }
66 else
67 {
68 printf ( " Left parentheses more than right parentheses \ n " ) ;
69 return 0;
70 }
71 } /* End of main () */
72
73 int match ( char a , char b )
74 {
75 if ( a == ’[ ’ && b == ’] ’)
76 return 1;
77
78 if ( a == ’{ ’ && b == ’} ’)
79 return 1;
80
81 if ( a == ’( ’ && b == ’) ’)
82 return 1;
83
84 return 0;
85

86 } /* End of match () */
87
88 void push ( char item )
89 {
90 if ( top ==( MAX -1) )
91 {
92 printf ( " Stack Overflow \ n " ) ;
93 return ;
94 }
95
96 top = top +1;
97 stack [ top ]= item ;
98
99 } /* End of push () */
100
101 char pop ()
102 {
103 if ( top == -1)
104 {
105 printf ( " Stack Underflow \ n " ) ;
106 exit (1) ;
107 }
108
109 return ( stack [ top - -]) ;
110
111 } /* End of pop () */

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 6 of 6

Module-II Sample Programs

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 7 of 6