﻿ Expression Parsing - Data Structures Handbook

# Expression Parsing

The way to write arithmetic expressions is known as a notation. An arithmetic expression can be written in three different but equivalent notations, i.e., without changing the essence or output of an expression.

There are generally 3 types of notations used to represent arithmetic expressions in computers.

## Infix Notation

Operators are written in-between their operands. This is the way we are used to writing expressions.

Infix notation needs extra information to make the order of evaluation of the operators clear: rules built into the language about operator precedence and associativity, and parentheses to allow users to override these rules. Infix notation is difficult to parse by computers in comparison to prefix or postfix notations.

Example: 3 + 4

## Postfix Notation (Reverse Polish Notation)

Here, Operators are written after their operands.

The order of evaluation of operators is always left-to-right, and brackets cannot be used to change this order. This notation is faster because reverse Polish calculators do not need expressions to be parenthesized, fewer operations need to be entered to perform typical calculations.

Example: 3 4 +

## Prefix Notation (Polish Notation)

Here, Operators are written before their operands.

Operators are evaluated left-to-right and brackets are unnecessary. The operators act on the two nearest values on the right.

Example: + 3 4