数据结构和算法

DSA - 主页 DSA - 概述 DSA - 环境设置 DSA - 算法基础 DSA - 渐近分析

数据结构

DSA - 数据结构基础 DSA - 数据结构和类型 DSA - 数组数据结构

链接列表

DSA - 链接列表数据结构 DSA - 双向链接列表数据结构 DSA - 循环链表数据结构

堆栈 &队列

DSA - 堆栈数据结构 DSA - 表达式解析 DSA - 队列数据结构

搜索算法

DSA - 搜索算法 DSA - 线性搜索算法 DSA - 二分搜索算法 DSA - 插值搜索 DSA - 跳跃搜索算法 DSA - 指数搜索 DSA - 斐波那契搜索 DSA - 子列表搜索 DSA - 哈希表

排序算法

DSA - 排序算法 DSA - 冒泡排序算法 DSA - 插入排序算法 DSA - 选择排序算法 DSA - 归并排序算法 DSA - 希尔排序算法 DSA - 堆排序 DSA - 桶排序算法 DSA - 计数排序算法 DSA - 基数排序算法 DSA - 快速排序算法

图形数据结构

DSA - 图形数据结构 DSA - 深度优先遍历 DSA - 广度优先遍历 DSA - 生成树

树数据结构

DSA - 树数据结构 DSA - 树遍历 DSA - 二叉搜索树 DSA - AVL 树 DSA - 红黑树 DSA - B树 DSA - B+ 树 DSA - 伸展树 DSA - 尝试 DSA - 堆数据结构

递归

DSA - 递归算法 DSA - 使用递归的汉诺塔 DSA - 使用递归的斐波那契数列

分而治之

DSA - 分而治之 DSA - 最大最小问题 DSA - 施特拉森矩阵乘法 DSA - Karatsuba 算法

贪婪算法

DSA - 贪婪算法 DSA - 旅行商问题(贪婪方法) DSA - Prim 最小生成树 DSA - Kruskal 最小生成树 DSA - Dijkstra 最短路径算法 DSA - 地图着色算法 DSA - 分数背包问题 DSA - 作业排序截止日期 DSA - 最佳合并模式算法

动态规划

DSA - 动态规划 DSA - 矩阵链乘法 DSA - Floyd Warshall 算法 DSA - 0-1 背包问题 DSA - 最长公共子序列算法 DSA - 旅行商问题(动态方法)

近似算法

DSA - 近似算法 DSA - 顶点覆盖算法 DSA - 集合覆盖问题 DSA - 旅行商问题(近似方法)

随机算法

DSA - 随机算法 DSA - 随机快速排序算法 DSA - Karger 最小割算法 DSA - Fisher-Yates 洗牌算法

DSA 有用资源

DSA - 问答 DSA - 快速指南 DSA - 有用资源 DSA - 讨论


Expression Parsing in Data Structure


An expression is any word or group of words or symbols that generates a value on evaluation. Parsing expression means analyzing the expression for its words or symbols depending on a particular criterion. Expression parsing is a term used in a programming language to evaluate arithmetic and logical expressions.

The way to write arithmetic expression 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. These notations are −

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

These notations are named as how they use operator in expression. We shall learn the same here in this chapter.

Infix Notation

We write expression in infix notation, e.g. a - b + c, where operators are used in-between operands. It is easy for us humans to read, write, and speak in infix notation but the same does not go well with computing devices. An algorithm to process infix notation could be difficult and costly in terms of time and space consumption.

Prefix Notation

In this notation, operator is prefixed to operands, i.e. 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 style, the operator is postfixed to the operands i.e., the operator is written after the operands. For example, ab+. This is equivalent to its infix notation a + b.

The following table briefly tries to show the difference in all three notations −

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 -

Parsing Expressions

As we have discussed, it is not a very efficient way to design an algorithm or program to parse infix notations. Instead, these 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 −

Operator Precendence

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

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 associativity of those operators. Here, both + and − are left associative, so the expression will be evaluated as (a + b) − c.

Precedence and associativity determines the order of evaluation of an expression. 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 above table shows the default behavior of operators. At any point of time in expression evaluation, the order can be altered by using parenthesis. For example −

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.

Postfix Evaluation Algorithm

We shall now look at the algorithm on how to evaluate postfix notation −

Step 1. Scan the expression from left to right 
Step 2. If it is an operand push it to stack 
Step 3. If it is an operator pull operand from stack and 
        perform operation 
Step 4. Store the output of step 3, back to stack 
Step 5. Scan the expression until all operands are consumed 
Step 6. Pop the stack and perform operation

Expression Parsing - Complete implementation

Following are the complete implementations of Expression Parsing (Conversion from infix notations to postfix notations) in various programming languages −

#include<stdio.h>
#include<string.h>
#include<ctype.h>
//char stack
char stack[25]; 
int top = -1; 
void push(char item) {
   stack[++top] = item; 
} 
char pop() {
   return stack[top--]; 
} 
//returns precedence of operators
int precedence(char symbol) {
   switch(symbol) {
      case '+': 
      case '-':
         return 2; 
         break; 
      case '*': 
      case '/':
         return 3; 
         break; 
      case '^': 
         return 4; 
         break; 
      case '(': 
      case ')': 
      case '#':
         return 1; 
         break; 
   } 
} 
//check whether the symbol is operator?
int isOperator(char symbol) {

   switch(symbol) {
      case '+': 
      case '-': 
      case '*': 
      case '/': 
      case '^': 
      case '(': 
      case ')':
         return 1; 
      break; 
         default:
         return 0; 
   } 
} 

//converts infix expression to postfix
void convert(char infix[],char postfix[]) {
   int i,symbol,j = 0; 
   stack[++top] = '#'; 
	
   for(i = 0;i<strlen(infix);i++) {
      symbol = infix[i]; 
		
      if(isOperator(symbol) == 0) {
         postfix[j] = symbol; 
         j++; 
      } else {
         if(symbol == '(') {
            push(symbol); 
         } else {
            if(symbol == ')') {
				
               while(stack[top] != '(') {
                  postfix[j] = pop(); 
                  j++; 
               } 
					
               pop();   //pop out (. 
            } else {
               if(precedence(symbol)>precedence(stack[top])) {
                  push(symbol); 
               } else {
					
                  while(precedence(symbol)<=precedence(stack[top])) {
                     postfix[j] = pop(); 
                     j++; 
                  } 
						
                  push(symbol); 
               }
            }
         }
      }
   }
	
   while(stack[top] != '#') {
      postfix[j] = pop(); 
      j++; 
   } 
	
   postfix[j]='\0';  //null terminate string. 
} 

//int stack
int stack_int[25]; 
int top_int = -1; 

void push_int(int item) {
   stack_int[++top_int] = item; 
} 

char pop_int() {
   return stack_int[top_int--]; 
} 

//evaluates postfix expression
int evaluate(char *postfix){

   char ch;
   int i = 0,operand1,operand2;

   while( (ch = postfix[i++]) != '\0') {
	
      if(isdigit(ch)) {
         push_int(ch-'0');  // Push the operand 
      } else {
         //Operator,pop two  operands 
         operand2 = pop_int();
         operand1 = pop_int();
			
         switch(ch) {
            case '+':
               push_int(operand1+operand2);
               break;
            case '-':
               push_int(operand1-operand2);
               break;
            case '*':
               push_int(operand1*operand2);
               break;
            case '/':
               push_int(operand1/operand2);
               break;
         }
      }
   }
	
   return stack_int[top_int];
}

void main() { 
   char infix[25] = "1*(2+3)",postfix[25]; 
   convert(infix,postfix); 
	
   printf("Infix expression is: %s
" , infix);
   printf("Postfix expression is: %s
" , postfix);
   printf("Evaluated expression is: %d
" , evaluate(postfix));
}

Output

Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Evaluated expression is: 5 
// C++ Code for Expression Parsing Using Stack
#include <iostream>
#include <string>
#include <cctype>
#include <stack>
// char stack
std::stack<char> stack;

void push(char item) {
    stack.push(item);
}
char pop() {
    char top = stack.top();
    stack.pop();
    return top;
}
// returns precedence of operators
int precedence(char symbol) {
    switch(symbol) {
        case '+':
        case '-':
            return 2;
        case '*':
        case '/':
            return 3;
        case '^':
            return 4;
        case '(':
        case ')':
        case '#':
            return 1;
    }
    return 0;
}
// check whether the symbol is an operator
int isOperator(char symbol) {
    switch(symbol) {
        case '+':
        case '-':
        case '*':
        case '/':
        case '^':
        case '(':
        case ')':
            return 1;
        default:
            return 0;
    }
}
// converts infix expression to postfix
void convert(const std::string& infix, std::string& postfix) {
    int j = 0;
    stack.push('#');
    for (char symbol : infix) {
        if (isOperator(symbol) == 0) {
            postfix += symbol;
            j++;
        } else {
            if (symbol == '(') {
                push(symbol);
            } else {
                if (symbol == ')') {
                    while (stack.top() != '(') {
                        postfix += pop();
                        j++;
                    }
                    stack.pop(); // pop out '('
                } else {
                    if (precedence(symbol) > precedence(stack.top())) {
                        push(symbol);
                    } else {
                        while (precedence(symbol) <= precedence(stack.top())) {
                            postfix += pop();
                            j++;
                        }
                        push(symbol);
                    }
                }
            }
        }
    }

    while (stack.top() != '#') {
        postfix += pop();
        j++;
    }

    postfix[j] = '\0'; // null terminate string
}
// evaluates postfix expression
int evaluate(const std::string& postfix) {
    std::stack<int> stack_int;
    int operand1, operand2;
    for (char ch : postfix) {
        if (std::isdigit(ch)) {
            stack_int.push(ch - '0'); // Push the operand
        } else {
            // Operator, pop two operands
            operand2 = stack_int.top();
            stack_int.pop();
            operand1 = stack_int.top();
            stack_int.pop();
            switch (ch) {
                case '+':
                    stack_int.push(operand1 + operand2);
                    break;
                case '-':
                    stack_int.push(operand1 - operand2);
                    break;
                case '*':
                    stack_int.push(operand1 * operand2);
                    break;
                case '/':
                    stack_int.push(operand1 / operand2);
                    break;
            }
        }
    }
    return stack_int.top();
}
int main() {
    std::string infix = "1*(2+3)", postfix;
    convert(infix, postfix);
    std::cout << "Infix expression is: " << infix << std::endl;
    std::cout << "Postfix expression is: " << postfix << std::endl;
    std::cout << "Evaluated expression is: " << evaluate(postfix) << std::endl;
    return 0;
}

Output

Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Evaluated expression is: 5
// Java Code for Expression Parsing Using Stack
import java.util.Stack;
public class Main {
    // char stack
    static Stack<Character> stack = new Stack<>();
    static void push(char item) {
        stack.push(item);
    }
    static char pop() {
        return stack.pop();
    }
    // returns precedence of operators
    static int precedence(char symbol) {
        switch (symbol) {
            case '+':
            case '-':
                return 2;
            case '*':
            case '/':
                return 3;
            case '^':
                return 4;
            case '(':
            case ')':
            case '#':
                return 1;
        }
        return 0;
    }
    // check whether the symbol is an operator
    static int isOperator(char symbol) {
        switch (symbol) {
            case '+':
            case '-':
            case '*':
            case '/':
            case '^':
            case '(':
            case ')':
                return 1;
            default:
                return 0;
        }
    }
    // converts infix expression to postfix
    static void convert(String infix, StringBuilder postfix) {
        int j = 0;
        stack.push('#');
        for (char symbol : infix.toCharArray()) {
            if (isOperator(symbol) == 0) {
                postfix.append(symbol);
                j++;
            } else {
                if (symbol == '(') {
                    push(symbol);
                } else {
                    if (symbol == ')') {
                        while (stack.peek() != '(') {
                            postfix.append(pop());
                            j++;
                        }
                        stack.pop(); // pop out '('
                    } else {
                        if (precedence(symbol) > precedence(stack.peek())) {
                            push(symbol);
                        } else {
                            while (precedence(symbol) <= precedence(stack.peek())) {
                                postfix.append(pop());
                                j++;
                            }
                            push(symbol);
                        }
                    }
                }
            }
        }
        while (stack.peek() != '#') {
            postfix.append(pop());
            j++;
        }
    }
    // evaluates postfix expression
    static int evaluate(String postfix) {
        Stack<Integer> stackInt = new Stack<>();
        int operand1, operand2;
        for (char ch : postfix.toCharArray()) {
            if (Character.isDigit(ch)) {
                stackInt.push(ch - '0'); // Push the operand
            } else {
                // Operator, pop two operands
                operand2 = stackInt.pop();
                operand1 = stackInt.pop();
                switch (ch) {
                    case '+':
                        stackInt.push(operand1 + operand2);
                        break;
                    case '-':
                        stackInt.push(operand1 - operand2);
                        break;
                    case '*':
                        stackInt.push(operand1 * operand2);
                        break;
                    case '/':
                        stackInt.push(operand1 / operand2);
                        break;
                }
            }
        }
        return stackInt.peek();
    }
    public static void main(String[] args) {
        String infix = "1*(2+3)";
        StringBuilder postfix = new StringBuilder();
        convert(infix, postfix);
        System.out.println("Infix expression is: " + infix);
        System.out.println("Postfix expression is: " + postfix);
        System.out.println("Evaluated expression is: " + evaluate(postfix.toString()));
    }
}

Output

Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Evaluated expression is: 5
class Main:
    stack = []
    @staticmethod
    def push(item):
        Main.stack.append(item)
    @staticmethod
    def pop():
        return Main.stack.pop()
    #returns precedence of operators
    @staticmethod
    def precedence(symbol):
        if symbol in ['+', '-']:
            return 2
        elif symbol in ['*', '/']:
            return 3
        elif symbol == '^':
            return 4
        elif symbol in ['(', ')', '#']:
            return 1
        return 0
    #check whether the symbol is an operator
    @staticmethod
    def is_operator(symbol):
        return symbol in ['+', '-', '*', '/', '^', '(', ')']
    @staticmethod
    def convert(infix):
        postfix = ""
        j = 0
        Main.push('#')
        for symbol in infix:
            if not Main.is_operator(symbol):
                postfix += symbol
                j += 1
            else:
                if symbol == '(':
                    Main.push(symbol)
                else:
                    if symbol == ')':
                        while Main.stack[-1] != '(':
                            postfix += Main.pop()
                            j += 1
                        Main.pop()  # pop out '('
                    else:
                        if Main.precedence(symbol) > Main.precedence(Main.stack[-1]):
                            Main.push(symbol)
                        else:
                            while Main.precedence(symbol) <= Main.precedence(Main.stack[-1]):
                                postfix += Main.pop()
                                j += 1
                            Main.push(symbol)
        while Main.stack[-1] != '#':
            postfix += Main.pop()
            j += 1
        return postfix
    @staticmethod
    def evaluate(postfix):
        stack_int = []
        for ch in postfix:
            if ch.isdigit():
                stack_int.append(int(ch))
            else:
                operand2 = stack_int.pop()
                operand1 = stack_int.pop()
                if ch == '+':
                    stack_int.append(operand1 + operand2)
                elif ch == '-':
                    stack_int.append(operand1 - operand2)
                elif ch == '*':
                    stack_int.append(operand1 * operand2)
                elif ch == '/':
                    stack_int.append(operand1 / operand2)
        return stack_int[0]
    @staticmethod
    def main():
        infix = "1*(2+3)"
        postfix = Main.convert(infix)
        print("Infix expression is:", infix)
        print("Postfix expression is:", postfix)
        print("Evaluated expression is:", Main.evaluate(postfix))
Main.main()

Output

Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Evaluated expression is: 5

Expression Parsing Using Stack

We can use different data structures to implement expression parsing. Check the implementation of Expression Parsing using Stack