Given a expression s containing just the pairs '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example: 
```
Input: s = "()"
Output: true
```

Example:

```
Input: s = "(]"
Output: false
```


MakyMyTrip

Backend Developer

Microsoft

Software Engineer

Nagarro

Valid Parentheses

Write a program to convert an Infix expression to Postfix form.

```
Input: 
Infix expression: A + B * C + D

Output: 
Postfix expression: ABC*+D+
```

Convert Infix expression to Postfix expression

Application in programming: 

**Recursion and function calling:** When a function is called, the current state of the program is pushed onto the stack. When the function returns, the state is popped from the stack to resume the previous function’s execution.

**Caching**: LRU is one of the example of using stack for caching.

**Expression evaluation:** Stack data structure is used to evaluate expressions in infix, postfix, and prefix notations. Operators and operands are pushed onto the stack, and operations are performed based on the stack’s top elements.

**Browser history:** Web browsers use stacks to keep track of the web pages you visit. Each time you visit a new page, the URL is pushed onto the stack, and when you hit the back button, the previous URL is popped from the stack.

**Balanced Parentheses:** Stack data structure is used to check if parentheses are balanced or not. An opening parenthesis is pushed onto the stack, and a closing parenthesis is popped from the stack. If the stack is empty at the end of the expression, the parentheses are balanced.

**Backtracking Algorithms:** The backtracking algorithm uses stacks to keep track of the states of the problem-solving process. The current state is pushed onto the stack, and when the algorithm backtracks, the previous state is popped from the stack.


**Application of Stack in real life:**

Call center systems.

Undo and Redo mechanism in text editors.

Stack of plates.

The history of a web browser is stored in the form of a stack.

Call logs, E-mails, and Google photos in any gallery are also stored in form of a stack.

YouTube downloads and Notifications are also shown in LIFO format(the latest appears first ).

Top Stack Interview Questions

1. Valid Parentheses

2. Convert Infix expression to Postfix expression

3. Application of stack data structure