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,

Operator Precedence

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:

To understand the implementation in C programming language, click here


All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Data Structure & Algorithms Topics