PDS LAB Test III  

(09.04.2007)

(Section : 2)

Submission deadline time: 3 p.m.

System Time :

For students with odd PC numbers

1.Write a program using stack to evaluate a given postfix expression.                                            [MARKS : 8]

Postfix notation is a mathematical notation wherein every operator follows all of its operands

In postfix notation the operators follow their operands; for instance, to add three and four one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 − 4 + 5" in conventional infix notation would be written "3 4 − 5 +"

Implement the stack using linked lists.

  Input : 3 4 +

  Output : 7

 Input : 5 8 * 7 −

 Output : 33

Input : 4 8 2 / - 9 + 7 3 + /

 Output : 0.9

Input : 9 1 2 4 * + 7 - /

Output : 4.5

 

2. Write a program using structure to implement a software timer.                                                      [MARKS :12]  

   Use the following structure & the following functions

struct sw_timer {
int hours;
int minutes;
int seconds;
} ;


void display(struct sw_timer *t); //Displays the timer
void update(struct sw_timer *t); //Updates the timer
void delay(void);                         //Introduces delay between updations

Hint : The delay function essentially consists of a loop whose exit condition value is  very high. The whole program will run in an infinite loop.

 

            Output: 00:00:00                          

                          00:00:01

                          00:00:02

                          (continuing)

                          00:00:58                       

                          00:00:59

                          00:01:00

                           & so on...

 

For students with even  PC numbers


1. Write a program that to implement a search( ) function that determines whether a specified name is in a given list.

The function prototype is  as follows -  int search(char *p[], char *name);                           [MARKS : 8]

  The first, p, is an array of char * pointers that point to strings containing names. The second, name, is a pointer to a string that points to the name being sought.

      Input :

                    List of names : Ram, Shyam, Seeta, Geeta

                  Search item: Shyam

      Output: Search string found at position 2 in list          

                    Search item: Mogambo     

     Output: Search string not found.                                                                                                                                                                                  

2. Write a program using stack that checks whether the parenthesisation of  a given expression is

correct or not.                                                                                                                                             [MARKS : 12]

Implement the stack using linked lists.

The following rules hold in case of parenthesisation checking:

(The corresponding illegal expressions are also cited)

  • Opening bracket should correspond to closing bracket

                              e.g  ((a+d)*[c-d] is illegal

  • Opening bracket should not immediately precede an operator

                              e.g    (*(a+d)) is illegal

  • Expression should not end with an operator

                             e.g    (a-d)* is illegal

  • Closing bracket should not immediately follow an operator 

                            e.g    (c/d)-(a*b)+) is illegal

  • Operators should not immediately precede or follow one another

                            e.g   (a+*d) is illegal

  • A closing bracket can be immediately followed by only a closing bracket or an operator but not by an opening bracket.

                            e.g    (a+b)(c*d) is illegal

  • Operand should not immediately precede an opening bracket or follow a closing bracket

                            e.g   {a(c+d)} or [(a*b)d] is illegal

  • While encountering multiple types of brackets make sure that you check the following condition: The last type of opening bracket must close before any other type of bracket closes.

                               e.g    {(a*d}) is illegal

  • Expression should not end with an opening bracket

                                e.g    {(a*d)}]+(c/d)-[ is illegal

Examples of legal expressions:

  1. [(a+b)*{(c/d)+e*f}]

  2. d+s

  3. (a+b*c-d)/(a-b*c+d)

  4. [{(s+d)}]

  5. {a+b*([a-d-f-g-h]/[s*d])}

  6. [{(b*b)-(t*a*c)}/{w*a*a}]