Skip to main content

8. Applications of Stack

 

Applications of Stack

Infix Notation

  • The operator is written in between the operands, e.g. A+B.
  • The reason why this notation is called infix is the place of operator in the expression.

Prefix Notation

  • In which the operator is written before the operands, e.g. +AB.
  • It is also called as polish notation.

Postfix Notation

  • The operator is written after the operands, e.g. AB+.
  • It is also known as suffix or reverse polish notation.
  • Postfix notation is the type of notation which is most suitable for a computer to calculate any expression. It is universally accepted notation for designing arithmetic and logical unit (ALU) of the CPU.
  • Any expression entered into the computer is first converted into postfix notation, stored in stack and then claculated.
  1. Convert the following infix expression into its equivalent postfix expression:
    (A+B^D)/(E-F)+G
    1. ABD^+EF-/G+
    2. ABD+^EF-/G+
    3. ABD+^EF/-G+
    4. ABD^+EF/-G+
  2. Convert the following infix to postfix expression:
    W+X*Y+(Z*A)
    1. WXY+*ZA*+
    2. WXY*+(za)*+
    3. WXY*+ZA*+
    4. W+XY*ZA
  3. Evaluate the given postfix expression:
    2 3 + 5 * 2 3 + 4 + *
    1. 210
    2. 225
    3. 220
    4. 200
  4. What is the output of the prefix expression:
    + - * 7 2 / 9 3 1
    1. 13
    2. 10
    3. 11
    4. 12

Recursion

  • Recursion is one of the most powerful tool in a programming language all it requires is to specify a reasonable condition and instruction set from right logic to solve a problem.
  • A recursive function with the following two properties is said to be well defined.
    • There must be certain arguments, called base values, for which the function does not refer to itself.
    • Each time the function does refer to itself, the argument of the function must be closer to a base value.
  • Examples of recursion:
    • Factorial function
    • Fibonacci sequence
    • Divide and conquer algorithms
  1. Find the output of the following pseudo code.
    2. void fun(int x)
    {
        if (x > 0)
        {
            printf("%d ", x);
            fun(x - 1);
        }
    }

    void main()
    {
        fun(4);
    }
  2. Find the output of the following pseudo code.
    3. void fun(int x)
    {
        if (x > 0)
        {
            fun(x - 1);
            printf("%d ", x);
        }
    }

    void main()
    {
        fun(4);
    }
  3. Find the output of the following pseudo code.
    4. void fun(int x)
    {
        if (x > 0)
        {
            printf("%d ", x);
            fun(x - 1);
            printf("%d ", x);
            fun(x - 1);
            printf("%d ", x);
        }
    }

    void main()
    {
        fun(3);
    }
  4. Find the output of the following pseudo code on n = 6.
    5. int x(int n)
    {
        if (n < 3)
            return 1;
        else
            return x(n - 1) + x(n - 1) + 1;
    }
  5. Consider the following recursive C function. If get(6) function is being called in main() then how many times will the get() function be invoked before returning to the main()?
    6. void get(int n)
    {
        if (n < 1)
            return;
        get(n - 1);
        get(n - 3);
        printf("%d", n);
    }
    1. 15
    2. 25
    3. 35
    4. 45
  6. Consider the following recursive C function that takes two arguments. What is the return value of the function foo() when it is called as foo(345, 10)?
    7. unsigned int foo(unsigned int n, unsigned int r)
    {
        if (n > 0)
            return (n % r + foo(n / r, r));
        else
            return 0;
    }
    1. 345
    2. 12
    3. 5
    4. 3
  7. Consider the following recursive C function that takes two arguments. What is the return value of the function foo() when it is called as foo(513, 2)?
    8. unsigned int foo(unsigned int n, unsigned int r)
    {
        if (n > 0)
            return (n % r + foo(n / r, r));
        else
            return 0;
    }
    1. 9
    2. 8
    3. 5
    4. 2
  8. Consider the following recursive function, what is the value of fun(3,4)?
    9. int fun(int x, int y)
    {
        if (x == 0)
            return y;
        return fun(x - 1, x + y);
    }
    1. 13
    2. 12
    3. 9
    4. 10
  9. What does the following function do?
    10. int fun(int x, int y)
    {
        if (y == 0)
            return 0;
        return (x + fun(x, y - 1));
    }
    1. x + y
    2. x + x * y
    3. x * y
    4. x ^ y
  10. What does the following function do?
    11. int fun(unsigned int n)
    {
        if (n == 0 || n == 1)
            return n;
        if (n % 3 != 0)
            return 0;
        return fun(n / 3);
    }
    1. It returns 1 when n is a multiple of 3, otherwise returns 0
    2. It returns 1 when n is a power of 3, otherwise returns 0
    3. It returns 0 when n is a multiple of 3, otherwise returns 1
    4. It returns 0 when n is a power of 3, otherwise returns 1

Prev Next

Comments

Post a Comment