# Data Structure - Expression Parsing - Data Structure & Algorithms

## Define Data Structure Notation

Notation is defined as a manner in which an arithmetic notation is written. Without changing the essence or output of a notation, In three different, equivalent notations arithmetic expressions can be written. The notations are named as they operate.

The notations are -

• Infix Notation
• Prefix (Polish) Notation
• Postfix (Reverse-Polish) Notation

### Infix Notation

Expressions are written in infix notation like a - b + c, between the operands, operators are used, such that they are easily readable, writable and easy to speak, but difficult in computing devices. The process of infix notation is difficult for an algorithm as it turns to be very costly in terms of time and space consumption.

### Prefix Notation

In Prefix notation, also known as Polish Notation, operator is prefixed to operands, i.e. operator is written ahead of operands. For insance, +ab. This is equal to the Infix notation a + b.

### Postfix Notation

In Postfix Notation, also known as Reversed Polish Notation, the operator is postfixed to the operands i.e., the operator is written after the operands. For instance, ab+. This is equal to the Infix notation a + b.

## What is the difference between Infix, Prefix and Postfix Notations?

The difference between the three notations is tabularized as:

 Sr. No. Infix Notation Prefix Notation Postfix Notation 1 a + b + a b a b + 2 (a + b) ∗c ∗ + a b c a b + c ∗ 3 a ∗ (b + c) ∗ a + b c a b c + ∗ 4 a / b + c / d + / a b / c d a b / c d / + 5 (a + b) ∗ (c + d) ∗ + a b + c d a b + c d + ∗ 6 ((a + b) ∗ c) - d - ∗ + a b c d a b + c ∗ d -

## What is Data Structure Parsing Expressions?

As it is not efficient to use the Infix notations, Infix notations are either converted into postfix or prefix notations before computing. This process is known as parsing of arithmetic expressions.

The arithmetic expression is parsed by taking care of the operator precendent and associativity.

### Precedence

Precedence of an operator decides which operator first takes the operand, when the operand is between two different operators. For instance,

As multiplication operation has precedence over addition, b * c will be evaluated first. A table of operator precedence is provided later.

### Associativity

The rule where the operators with the same precedence appear in the expression is described by Associativity. For instance, in expression a + b − c, both + and – have the same precedence, then which part of the expression will be evaluated first, is determined by associativity of those operators. Here, both + and − are left associative, so the expression will be evaluated as (a + b) − c.

The order of the evaluation of the expression is determined by both precedence and associativity together.

The default behaviour of the operators is shown in the table. Following is an operator precedence and associativity table (highest to lowest) −

 Sr. No. Operator Precedence Associativity 1 Exponentiation ^ Highest Right Associative 2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left Associative 3 Addition ( + ) & Subtraction ( − ) Lowest Left Associative

The order in the expression evaluation can be altered by parenthesis. For instance -

In a + b*c, the expression part b*c will be evaluated first, with multiplication as precedence over addition. We here use parenthesis for a + b to be evaluated first, like (a + b)*c.

## How to evaluate Postfix Algorithm?

The algorithm to evaluate the postfix notation is: