Stack is a type of data structure that works on LIFO (Last in First out). LIFO is a special type of sequence where priority is given to the data that is entered last. Push and Pop two operations are performed in the stack. Push is used to add the data to the stack and pop is used to remove the data from the stack. In both the operation of push and pop, data is added and removed from the top of the stack. In stack, there are 2 operations for insertion and deletion from the top.
1.push(): For inserting the value in the stack push() operation is used.
2.pop(): For deletion pop() function is used from the top.
Example. A pile of plates
Expression parsing: The way to write arithmetic expression is known as a notation. An arithmetic expression can be written in three different but equivalent notations. These notations are −
- Infix Notation
- Prefix (Polish) Notation
- Postfix (Reverse-Polish) Notation
Infix Notation:
In infix notation, operators are used in-between operands. For example, a+b+c. It is easy to read and write in infix notation but for computing devices, it is not true. An algorithm to process infix notation could be difficult and costly in terms of time and space consumption.
Prefix Notation:
In this notation, the operator is written ahead of operands. For example, +ab. This is equivalent to its infix notation a + b. Prefix notation is also known as Polish Notation.
Postfix Notation:
This notation style is known as Reversed Polish Notation. In this notation, the operator is written at the end of the operands. For example, ab+. This is equivalent to its infix notation a + b.
Infix notations are not easy for computer devices. So, infix notations are first converted into either postfix or prefix notations and then computed.
To parse any arithmetic expression, we need to take care of operator precedence and associativity also.
Precedence:
When an operand is in between two different operators, which operator will take the operand first, is decided by the precedence of an operator over others. For example −
As multiplication operation has precedence over addition, b * c will be evaluated first.
Associativity:
Associativity describes the rule where operators with the same precedence appear in an expression. For example, in expression a + b − c, both + and – have the same precedence, then which part of the expression will be evaluated first, is determined by the associativity of those operators. Here, both + and − are left-associative, so the expression will be evaluated as (a + b) − c.
