Expression Parsing: Part 1

July 23, 2020 7048

An Arithmetic expression can be written in three different but equivalent ways called notations, based on the use of the operator in the expression. They are,

1. Infix Notation
2. Prefix (Polish) Notation
3. Postfix (Reverse Polish) Notation

Infix Notation

Infix notation is of the form - operator in between operands. Eg, a + b * c. It is easy for humans to write and understand infix notation. But deriving an algorithm for evaluating an infix notation is difficult and costly in terms of space and time complexity. So, we convert infix notation to one of the latter notations before evaluating the result.

Prefix Notation

In prefix notation, the operators are prefixed to operands, eg, the equivalent prefix notation for Infix a+b is +ab. This notation is also termed as Polish Notation.

Postfix Notation

In Postfix Notation, the operators are postfixed to operands, eg, the postfix notation ab+ is equivalent to infix notation a+b. This style of notation is also called Reverse Polish Notation. Later in this section, we will study an algorithm which converts infix to prefix and postfix notations.

To convert an expression from infix to prefix or postfix, we need to take care of operator Precedence order and Associativity.

Precedence Order

When there are more than one operator in the expression, then the order of their evaluation is decided by the operator precedence over others. For eg, consider the expression a + b * c, here b*c should be evaluated first as the precedence of multiplication is higher than addition. The priority or precedence of the operators is shown in the tabular format later in this section.

Associativity

The rule for operators having the same precedence order is described by their Associativity. For example, consider the expression a + b - c. Here, the precedence order of “+” and “-” is the same and both are left associative, therefore, (a+b) is evaluated first.

The Binary operator’s precedence order (top-highest to down-lowest) and associativity is shown below in the table.

 Sr. no Operator Associativity 1 Exponentiation (^) Right Associative 2 Multiplication(*) and Division (/) Left Associative 3 Addition(+) and Subtraction(-) Left Associative

Note: The above behavior can be altered using parentheses in the expression. For example, in the expression (a+b)*c, the a+b part of the expression will be evaluated first in spite of multiplication having higher precedence than addition.

Infix to Postfix Algorithm

To convert infix notation to postfix notation, we will use a stack data structure and store the postfix result into a variable output. The algorithm is as follows,

1. Scan the infix expression from left to right.
2. If the scanned character is an operand, append it to the output variable.
3. Else if it is an operator, then check the following condition.
3.1  If the stack is empty or the top of the stack contains open braces ‘(‘ or the precedence order of the scanned (incoming) operator is greater than the operator at the top of the stack, then push the scanned (incoming) operator to the stack.
3.2  Else pop all the operators from the stack which are greater than or equal to the scanned operator or until open parenthesis is encountered or the stack becomes empty, and push the scanned operator to the stack.
4. If the scanned character is an open parenthesis “(“, then push it onto the stack.
5. If the scanned character is a close parenthesis “)”, then pop all the operators to the output until open parenthesis “(“ is encountered, and discard the open parenthesis and the scanned character (close parenthesis).
6. Repeat steps from 2 to 5 until all the characters in the infix are scanned.
7. Pop all the remaining operators and empty the stack to the output variable.
8. Print the output variable.

Find below the working of the Infix to Postfix algorithm for expression a * (b + c) / d,

 Steps Stack Scanned Character Output Step used from Infix to Prefix algorithm Initially [Empty Stack] 1 [Empty Stack] d d 4. 2 / / d 5.1 3 /( ( d 6. 4 /( c dc 4. 5 /(+ + dc 5.1 6 /(+ b dcb 4. 7 / ) dcb+ 7. 8 * * dcb+/ 5.2 9 * a dcb+/a 4. 10 [Empty Stack] End dcb+/a* 9 11 Reverse the output variable *a/+bcd 10.

Therefore, the Postfix expression of a * (b + c) / d is abc+*d/

• C/C++
• Python
• Java
#include <iostream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
// Check if a character is operator(including '(') or not.
int operatorOrNot(char ch)
{
if (ch == '^' || ch == '/' || ch == '*' || ch == '+' || ch == '-' || ch == '(')
return 1;
return 0;
}
// Priority of operators.
int Priority(char op)
{
if (op == '^')
return 3;
else if (op == '/' || op == '*')
return 2;
else if (op == '+' || op == '-')
return 1;
// When char is '(', While loop should not be executed.
return INT8_MAX;
}
string InfixToPostfix(string expression)
{
string output;
stack<char> Stack;
for (int i = 0; i < expression.length(); i++)
{
char character = expression[i];
// if character is operand.
if (isalnum(character))
{
output.push_back(character);
}
// if character is an operator or '('.
else if (operatorOrNot(character))
{
// Pop and append operators greater than scanned operator.
while (!Stack.empty() && Stack.top() != '(' && Priority(Stack.top()) >= Priority(character))
{
output.push_back(Stack.top());
Stack.pop();
}
Stack.push(character);
}
// if character is ')'
//   then pop until '('.
else if (character == ')')
{
while (Stack.top() != '(')
{
output.push_back(Stack.top());
Stack.pop();
}
Stack.pop();
}
}
// Pop all remaining elements.
while (!Stack.empty())
{
output.push_back(Stack.top());
Stack.pop();
}
return output;
}
int main()
{
char infix[] = "a*(b+c)/d";
cout << "Infix: " << infix << endl;
cout << "Postfix: " << InfixToPostfix(infix);
}

# Priority of operators.
def Priority(char):
if char is "^":
return 3
elif char is "/" or char is "*":
return 2
elif char is "+" or char is "-":
return 1
# When char is '(' loop should not be executed.
return float("inf")

def InfixToPostfix(expression):
output = ""
stack = []
for character in expression:
# if character is operand.
if character.isalnum():
output += character
# if character is an operator or '('.
elif character in ["^", "*", "/", "+", "-", "("]:
# Pop and append operators greater than scanned operator.
while (
len(stack) > 0
and stack[-1] != "("
and Priority(stack[-1]) >= Priority(character)
):
output += stack.pop()
stack.append(character)
elif character is ")":
# if character is ')'
#   then pop until '('.
while stack[-1] != "(":
output += stack.pop()
stack.pop()
# Pop all remaining elements.
while len(stack) > 0:
output += stack.pop()
return output

if __name__ == "__main__":
infix = "a*(b+c)/d"
print(f"Infix: {infix}")
print(f"Postfix: {InfixToPostfix(infix)}")

import java.util.Stack;

public class MyClass {
public static void main(String args[]) {
String infix = "a*(b+c)/d";
System.out.println("Infix: " + infix);
System.out.println("Postfix: " + InfixToPostfix(infix));
}

// Check if a character is operator(including '(') or not.
public static boolean operatorOrNot(char ch) {
if (ch == '^' || ch == '/' || ch == '*' || ch == '+' || ch == '-' || ch == '(')
return true;
return false;
}

// Priority of operators.
public static int Priority(char op) {
if (op == '^')
return 3;
else if (op == '/' || op == '*')
return 2;
else if (op == '+' || op == '-')
return 1;
// When char is '(', While loop should not be executed.
return Integer.MAX_VALUE;
}

public static StringBuilder InfixToPostfix(String expression) {
StringBuilder output = new StringBuilder();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < expression.length(); i++) {
char character = expression.charAt(i);
// if character is operand.
if (Character.isLetterOrDigit(character)) {
output.append(character);
}
// if character is an operator or '('.
else if (operatorOrNot(character)) {
// Pop and append operators greater than scanned operator.
while (!stack.isEmpty() && stack.peek() != '(' && Priority(stack.peek()) >= Priority(character)) {
output.append(stack.pop());
}
stack.push(character);
}
// if character is ')'
// then pop until '('.
else if (character == ')') {
while (stack.peek() != '(') {
output.append(stack.pop());
}
stack.pop();
}
}
// Pop all remaining elements.
while (!stack.isEmpty()) {
output.append(stack.pop());
}
return output;
}
}


Output

Infix: a*(b+c)/d Postfix: abc+*d/

Infix to Prefix Algorithm

Steps to convert Infix expression to Prefix expression is same as Infix to Postfix with some additional steps involved. In the following algorithm, steps 1, 2 and 10 are added.

1. Reverse the infix expression.
2. Convert all open parenthesis “(“ to close parenthesis “)” and vice versa. (On executing step 1, the parenthesis present in the expression will also get reversed which we don’t want, hence this step is required.)
3. Scan the infix expression from left to right.
4. If the scanned character is an operand, append it to the output variable.
5. Else if it is an operator, then check the following condition.
5.1  If the stack is empty or the top of the stack contains open braces ‘(‘ or the precedence order of the scanned (incoming) operator is greater than the operator at the top of the stack, then push the (scanned) incoming operator to the stack.
5.2  Else pop all the operators from the stack which are greater than or equal to the scanned operator or until open parenthesis is encountered or the stack becomes empty, and push the scanned operator to the stack.
6. If the scanned character is an open parenthesis “(“, then push it onto the stack.
7. If the scanned character is a close parenthesis “)”, then pop all the operators to the output until open parenthesis “(“ is encountered, and discard the open parenthesis and the scanned character (close parenthesis).
8. Repeat steps from 4 to 7 until all the characters in infix are scanned.
9. Pop all the remaining operators and empty the stack to the output variable.
10. Reverse the output variable.
11. Print the output variable.

Find below the working of the Infix to Prefix algorithm for expression a * (b + c) / d,

After performing steps 1 and 2, the expression becomes d / (c + b ) * a

 Steps Stack Scanned Character Output Step used from Infix to Prefix algorithm Initially [Empty Stack] 1 [Empty Stack] d d 4. 2 / / d 5.1 3 /( ( d 6. 4 /( c dc 4. 5 /(+ + dc 5.1 6 /(+ b dcb 4. 7 / ) dcb+ 7. 8 * * dcb+/ 5.2 9 * a dcb+/a 4. 10 [Empty Stack] End dcb+/a* 9 11 Reverse the output variable *a/+bcd 10.

Therefore, the Prefix expression of a * (b + c) / d is *a/+bcd/

• C/C++
• Python
• Java
#include <iostream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
// Check if a character is operator(including '(') or not.
int operatorOrNot(char ch)
{
if (ch == '^' || ch == '/' || ch == '*' || ch == '+' || ch == '-' || ch == '(')
return 1;
return 0;
}
// Priority of operators.
int Priority(char op)
{
if (op == '^')
return 3;
else if (op == '/' || op == '*')
return 2;
else if (op == '+' || op == '-')
return 1;
// When char is '(', While loop should not be executed.
return INT8_MAX;
}
string InfixToPrefix(string expression)
{
reverse(expression.begin(), expression.end());
string output;
stack<char> Stack;
for (int i = 0; i < expression.length(); i++)
{
char character = expression[i];
if (character == '(')
character = ')';
else if (character == ')')
character = '(';
// if character is operand.
if (isalnum(character))
{
output.push_back(character);
}
// if character is an operator or '('.
else if (operatorOrNot(character))
{
// Pop and append operators greater than scanned operator.
while (!Stack.empty() && Stack.top() != '(' && Priority(Stack.top()) >= Priority(character))
{
output.push_back(Stack.top());
Stack.pop();
}
Stack.push(character);
}
// if character is ')'
//   then pop until '('.
else if (character == ')')
{
while (Stack.top() != '(')
{
output.push_back(Stack.top());
Stack.pop();
}
Stack.pop();
}
}
// Pop all remaining elements.
while (!Stack.empty())
{
output.push_back(Stack.top());
Stack.pop();
}
reverse(output.begin(), output.end());
return output;
}
int main()
{
string infix = "a*(b+c)/d";
cout << "Infix: " << infix << endl;
cout << "Postfix: " << InfixToPrefix(infix);
}

# Priority of operators.
def Priority(char):
if char is "^":
return 3
elif char is "/" or char is "*":
return 2
elif char is "+" or char is "-":
return 1
# When char is '(' loop should not be executed.
return float("inf")

def InfixToPrefix(expression):
# Reverse the expression.
expression = expression[::-1]
output = ""
stack = []
for character in expression:
# Replace '(' to ')' and vice versa.
if character is "(":
character = ")"
elif character is ")":
character = "("
# if character is operand.
if character.isalnum():
output += character
# if character is an operator or '('.
elif character in ["^", "*", "/", "+", "-", "("]:
# Pop and append operators greater than scanned operator.
while (
len(stack) > 0
and stack[-1] != "("
and Priority(stack[-1]) >= Priority(character)
):
output += stack.pop()
stack.append(character)
elif character is ")":
# if character is ')'
#   then pop until '('.
while stack[-1] != "(":
output += stack.pop()
stack.pop()
# Pop all remaining elements.
while len(stack) > 0:
output += stack.pop()
return output[::-1]

if __name__ == "__main__":
infix = "a*(b+c)/d"
print(f"Infix: {infix}")
print(f"Prefix: {InfixToPrefix(infix)}")

import java.util.Stack;

public class MyClass {
public static void main(String args[]) {
String infix = "a*(b+c)/d";
System.out.println("Infix: " + infix);
System.out.println("Prefix: " + InfixToPrefix(infix));
}

// Check if a character is operator(including '(') or not.
public static boolean operatorOrNot(char ch) {
if (ch == '^' || ch == '/' || ch == '*' || ch == '+' || ch == '-' || ch == '(')
return true;
return false;
}

// Priority of operators.
public static int Priority(char op) {
if (op == '^')
return 3;
else if (op == '/' || op == '*')
return 2;
else if (op == '+' || op == '-')
return 1;
// When char is '(', While loop should not be executed.
return Integer.MAX_VALUE;
}

public static StringBuilder InfixToPrefix(String expression) {
StringBuilder output = new StringBuilder();
Stack<Character> stack = new Stack<>();
// Reverse the String
for (int i = expression.length() - 1; i >= 0; i--) {
char character = expression.charAt(i);
// Replace '(' to ')' and vice versa.
if (character == '(')
character = ')';
else if (character == ')')
character = '(';
// if character is operand.
if (Character.isLetterOrDigit(character)) {
output.append(character);
}
// if character is an operator or '('.
else if (operatorOrNot(character)) {
// Pop and append operators greater than scanned operator.
while (!stack.isEmpty() && stack.peek() != '(' && Priority(stack.peek()) >= Priority(character)) {
output.append(stack.pop());
}
stack.push(character);
}
// if character is ')'
// then pop until '('.
else if (character == ')') {
while (stack.peek() != '(') {
output.append(stack.pop());
}
stack.pop();
}
}
// Pop all remaining elements.
while (!stack.isEmpty()) {
output.append(stack.pop());
}
return output.reverse();
}
}


Output

Infix: a*(b+c)/d Prefix: *a/+bcd

Next:

Expression Parsing: Part 2

Liked the post?
Editor's Picks
0 COMMENT

Please login to view or add comment(s).