Stacks Programming Practice

Implementation Problems

1. Write a C program to implement a stack using a global array and a top variable (without using structures). Your program should include functions for push(), pop(), and display().
2. Write a C program to implement a stack using a structure. The structure should contain an array to hold the stack elements and an integer top.
3. Implement the helper functions peek(), isFull(), and isEmpty() for your stack implementation.
4. Modify your stack implementation to use a dynamic array. The program should initially allocate a small amount of memory and then double the capacity of the array whenever the stack becomes full.
5. Using your stack implementation, write a program that checks if an expression has balanced parentheses (i.e., '()', '{}', '[]'). The program should be able to validate expressions like (a + {b * [c - d]}) and invalidate ones like (a + b] or (a + b.

Expression Conversion Problems

1. Infix to Postfix Conversion
   Convert the following infix expressions to postfix:

   a + b * c

   (a + b) * c

   a $ b $ c   (where '$' is exponentiation and is right-associative)

   a * b + c * d + e * f

   a $ b * c - d + e / f / (g + h)

   ((a + (b - c) * d) $ e + f)

2. Infix to Prefix Conversion
   Convert the following infix expressions to prefix:

   (a + b) * (c + d)

   a - b / (c * d $ e)

   ((a + (b - c) * d) $ e + f)

   a $ b * c - d + e / f / (g + h)

3. Other Conversions
   Convert the postfix expression

   ABC/-AK/L-*

   to its equivalent prefix expression.
4. Convert the postfix expression

   ABC/-AK/L-*

   to its equivalent infix expression.
5. Convert the prefix expression

   *-A/BC-/AKL

   to its equivalent postfix expression.
6. Convert the prefix expression

   *-A/BC-/AKL

   to its equivalent infix expression.

Expression Evaluation Problems

1. Expression Evaluation Problems
   These problems require you to use a stack to compute the value of an expression. Show the state of the stack after processing each symbol.
2. Postfix Evaluation
   Evaluate the following postfix expressions:

   2 3 + 4 *

   6 2 3 + - 3 8 2 / + * 2 $ 3 +

   8 2 / 3 - 4 2 * +

   5 6 2 + * 8 4 / -

3. Prefix Evaluation
   Evaluate the following prefix expressions:

   - + 8 / 6 3 2

   - + 7 * 4 5 + 2 0

   + - * 2 3 5 / 8 4

   * + 6 5 - 4 2