- Data Structures & Algorithms
- DSA - Home
- DSA - Introduction
- DSA - Environment Setup
- DSA - Algorithms Basics
- DSA - Characteristics of Algorithms
- DSA - Asymptotic Analysis
- Data Structures
- DSA - Data Structure Basics
- DSA - Data Structures and Types
- DSA - Array Data Structure
- Linked Lists
- DSA - Linked List Data Structure
- DSA - Single Linked List Data Structure
- DSA - Doubly Linked List Data Structure
- DSA - Circular Linked List Data Structure
- Stack & Queue
- DSA - Stack Data Structure
- DSA - Expression Parsing
- DSA - Queue Data Structure
- Searching Algorithms
- DSA - Searching Algorithms
- DSA - Linear Search Algorithm
- DSA - Binary Search Algorithm
- DSA - Interpolation Search
- DSA - Jump Search Algorithm
- DSA - Exponential Search
- DSA - Fibonacci Search
- DSA - Sublist Search
- DSA - Hash Table
- Sorting Algorithms
- DSA - Sorting Algorithms
- DSA - Bubble Sort Algorithm
- DSA - Insertion Sort Algorithm
- DSA - Selection Sort Algorithm
- DSA - Merge Sort Algorithm
- DSA - Shell Sort Algorithm
- DSA - Heap Sort
- DSA - Bucket Sort Algorithm
- DSA - Counting Sort Algorithm
- DSA - Radix Sort Algorithm
- DSA - Quick Sort Algorithm
- Graph Data Structure
- DSA - Graph Data Structure
- DSA - Depth First Traversal
- DSA - Breadth First Traversal
- DSA - Spanning Tree
- Tree Data Structure
- DSA - Tree Data Structure
- DSA - Tree Traversal
- DSA - Binary Search Tree
- DSA - AVL Tree
- DSA - Red Black Trees
- DSA - B Trees
- DSA - B+ Trees
- DSA - Splay Trees
- DSA - Tries
- DSA - Heap Data Structure
- Recursion
- DSA - Recursion Algorithms
- DSA - Tower of Hanoi Using Recursion
- DSA - Fibonacci Series Using Recursion
- Divide and Conquer
- DSA - Divide and Conquer
- DSA - Max-Min Problem
- DSA - Strassen's Matrix Multiplication
- DSA - Karatsuba Algorithm
- Greedy Algorithms
- DSA - Greedy Algorithms
- DSA - Travelling Salesman Problem (Greedy Approach)
- DSA - Prim's Minimal Spanning Tree
- DSA - Kruskal's Minimal Spanning Tree
- DSA - Dijkstra's Shortest Path Algorithm
- DSA - Map Colouring Algorithm
- DSA - Fractional Knapsack Problem
- DSA - Job Sequencing with Deadline
- DSA - Optimal Merge Pattern Algorithm
- Dynamic Programming
- DSA - Dynamic Programming
- DSA - Matrix Chain Multiplication
- DSA - Floyd Warshall Algorithm
- DSA - 0-1 Knapsack Problem
- DSA - Longest Common Subsequence Algorithm
- DSA - Travelling Salesman Problem (Dynamic Approach)
- Approximation Algorithms
- DSA - Approximation Algorithms
- DSA - Vertex Cover Algorithm
- DSA - Set Cover Problem
- DSA - Travelling Salesman Problem (Approximation Approach)
- Randomized Algorithms
- DSA - Randomized Algorithms
- DSA - Randomized Quick Sort Algorithm
- DSA - Karger’s Minimum Cut Algorithm
- DSA - Fisher-Yates Shuffle Algorithm
Data Structures & Algorithms - Expression Parsing
 Share with a Friend |
Expression Parsing
Expression Parsing in Data Structures and Algorithms
📘 What is Expression Parsing?
Expression parsing is the process of analyzing an arithmetic or logical expression to determine its structure and meaning. It is commonly used in compilers, interpreters, calculators, and various programming tools.
Expressions can be written in different notations:
- Infix: (A + B) – operator is between operands
- Prefix (Polish): + A B – operator is before operands
- Postfix (Reverse Polish): A B + – operator is after operands
🧠 Why Do We Parse Expressions?
- To evaluate expressions programmatically
- To convert infix to postfix or prefix
- To build syntax trees
- To detect syntax errors
🔁 Steps in Expression Parsing:
- Tokenization – break input into operators, operands, and parentheses.
- Shunting Yard Algorithm – convert infix to postfix.
- Postfix Evaluation – using a stack.
- Parentheses Matching – check if the expression is balanced.
🛠️ Infix to Postfix Conversion Algorithm (Using Stack)
Steps:
- If operand, add to output.
- If (, push to stack.
- If ), pop until (.
- If operator, pop higher precedence from stack, then push current.
✅ Infix to Postfix Example:
Input (Infix):
A + B * C
Output (Postfix):
A B C * +
💻 Implementation in C, C++, Java, Python
- ✅ Convert infix to postfix
- ✅ Evaluate postfix
- ✅ Handle real inputs with output
🔁 Infix to Postfix Conversion
✅ Rules for Conversion
-
Operands go directly to the output.
-
Operators are pushed to the stack (based on precedence).
-
Left parentheses
(are pushed to the stack. -
Right parentheses
)pop all operators until a(is encountered.
🧠 Operator Precedence
^ > * / > + -
Associativity:
- ^ is right-to-left
- others are left-to-right
Infix expression:
A+B*(C^D-E)^(F+G*H)-I
The equivalent postfix is:
ABCD^E-FGH*+^*+I-
Program: Infix to Postfix
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define SIZE 100
char stack[SIZE];
int top = -1;
int precedence(char op) {
if(op == '^') return 3;
if(op == '*' || op == '/') return 2;
if(op == '+' || op == '-') return 1;
return 0;
}
void push(char ch) {
stack[++top] = ch;
}
char pop() {
return stack[top--];
}
int isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^';
}
void infixToPostfix(char* exp) {
for(int i = 0; exp[i]; i++) {
char ch = exp[i];
if(isalnum(ch)) {
printf("%c", ch);
} else if(ch == '(') {
push(ch);
} else if(ch == ')') {
while(stack[top] != '(') {
printf("%c", pop());
}
pop(); // remove '('
} else {
while(top != -1 && precedence(stack[top]) >= precedence(ch)) {
printf("%c", pop());
}
push(ch);
}
}
while(top != -1) {
printf("%c", pop());
}
}
int main() {
char exp[] = "A+B*(C^D-E)^(F+G*H)-I";
printf("Postfix: ");
infixToPostfix(exp);
return 0;
}
Output
Postfix: ABCD^E-FGH*+^*+I-
#include <iostream>
#include <stack>
#include <cctype>
using namespace std;
int precedence(char op) {
if(op == '^') return 3;
if(op == '*' || op == '/') return 2;
if(op == '+' || op == '-') return 1;
return 0;
}
bool isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^';
}
string infixToPostfix(string exp) {
string result;
stack<char> s;
for(char ch : exp) {
if(isalnum(ch)) {
result += ch;
} else if(ch == '(') {
s.push(ch);
} else if(ch == ')') {
while(!s.empty() && s.top() != '(') {
result += s.top(); s.pop();
}
s.pop(); // remove '('
} else {
while(!s.empty() && precedence(s.top()) >= precedence(ch)) {
result += s.top(); s.pop();
}
s.push(ch);
}
}
while(!s.empty()) {
result += s.top(); s.pop();
}
return result;
}
int main() {
string exp = "A+B*(C^D-E)^(F+G*H)-I";
cout << "Postfix: " << infixToPostfix(exp);
return 0;
}
Output
Postfix: ABCD^E-FGH*+^*+I-
import java.util.Stack;
public class InfixToPostfix {
static int precedence(char ch) {
switch (ch) {
case '^': return 3;
case '*': case '/': return 2;
case '+': case '-': return 1;
default: return -1;
}
}
public static String convert(String exp) {
StringBuilder result = new StringBuilder();
Stack<Character> stack = new Stack<>();
for (char ch : exp.toCharArray()) {
if (Character.isLetterOrDigit(ch)) {
result.append(ch);
} else if (ch == '(') {
stack.push(ch);
} else if (ch == ')') {
while (!stack.isEmpty() && stack.peek() != '(')
result.append(stack.pop());
stack.pop();
} else {
while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(ch))
result.append(stack.pop());
stack.push(ch);
}
}
while (!stack.isEmpty())
result.append(stack.pop());
return result.toString();
}
public static void main(String[] args) {
String expr = "A+B*(C^D-E)^(F+G*H)-I";
System.out.println("Postfix: " + convert(expr));
}
}
Output
Postfix: ABCD^E-FGH*+^*+I-
def precedence(op):
if op == '^': return 3
if op in ('*', '/'): return 2
if op in ('+', '-'): return 1
return 0
def infix_to_postfix(exp):
stack = []
result = ''
for ch in exp:
if ch.isalnum():
result += ch
elif ch == '(':
stack.append(ch)
elif ch == ')':
while stack and stack[-1] != '(':
result += stack.pop()
stack.pop() # remove '('
else:
while stack and precedence(stack[-1]) >= precedence(ch):
result += stack.pop()
stack.append(ch)
while stack:
result += stack.pop()
return result
expr = "A+B*(C^D-E)^(F+G*H)-I"
print("Postfix:", infix_to_postfix(expr))
Output
Postfix: ABCD^E-FGH*+^*+I-
✅ Postfix Expression Evaluation
Let’s say the expression is:
5 6 2 ^ - 3 4 * + ^ * + 1 -
Which is the postfix form of:
5 + 6 * (2 ^ 3 - 4) ^ (3 + 4 * 2) - 1
We’ll now evaluate this using a stack-based approach.
🔁 Algorithm (Postfix Evaluation)
- Initialize an empty stack.
- Read symbols from left to right:
- If operand, push it to the stack.
- If operator, pop top two elements, apply the operator, push result back.
- After reading all, the result is on top of the stack.
✅ Implementation in C, C++, Java, Python Languages
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int val) {
stack[++top] = val;
}
int pop() {
return stack[top--];
}
int evaluatePostfix(char* exp) {
int i = 0;
while (exp[i]) {
if (isdigit(exp[i])) {
push(exp[i] - '0');
} else {
int val2 = pop();
int val1 = pop();
switch (exp[i]) {
case '+': push(val1 + val2); break;
case '-': push(val1 - val2); break;
case '*': push(val1 * val2); break;
case '/': push(val1 / val2); break;
case '^': push(pow(val1, val2)); break;
}
}
i++;
}
return pop();
}
int main() {
char exp[] = "52+83-*4/";
printf("Result: %d\n", evaluatePostfix(exp));
return 0;
}
Output
Expression: 52+83-*4/
Infix: ((5+2)*(8-3))/4
Result: 8
#include <iostream>
#include <stack>
#include <cmath>
using namespace std;
int evaluate(string exp) {
stack<int> s;
for (char ch : exp) {
if (isdigit(ch)) {
s.push(ch - '0');
} else {
int b = s.top(); s.pop();
int a = s.top(); s.pop();
switch (ch) {
case '+': s.push(a + b); break;
case '-': s.push(a - b); break;
case '*': s.push(a * b); break;
case '/': s.push(a / b); break;
case '^': s.push(pow(a, b)); break;
}
}
}
return s.top();
}
int main() {
string exp = "52+83-*4/";
cout << "Result: " << evaluate(exp) << endl;
return 0;
}
Output
Expression: 52+83-*4/
Infix: ((5+2)*(8-3))/4
Result: 8
import java.util.*;
public class PostfixEval {
public static int evaluate(String exp) {
Stack<Integer> stack = new Stack<>();
for (char ch : exp.toCharArray()) {
if (Character.isDigit(ch)) {
stack.push(ch - '0');
} else {
int b = stack.pop();
int a = stack.pop();
switch (ch) {
case '+': stack.push(a + b); break;
case '-': stack.push(a - b); break;
case '*': stack.push(a * b); break;
case '/': stack.push(a / b); break;
case '^': stack.push((int)Math.pow(a, b)); break;
}
}
}
return stack.pop();
}
public static void main(String[] args) {
String exp = "52+83-*4/";
System.out.println("Result: " + evaluate(exp));
}
}
Output
Expression: 52+83-*4/
Infix: ((5+2)*(8-3))/4
Result: 8
def evaluate_postfix(expression):
stack = []
for ch in expression:
if ch.isdigit():
stack.append(int(ch))
else:
b = stack.pop()
a = stack.pop()
if ch == '+': stack.append(a + b)
elif ch == '-': stack.append(a - b)
elif ch == '*': stack.append(a * b)
elif ch == '/': stack.append(a // b)
elif ch == '^': stack.append(a ** b)
return stack[0]
exp = "52+83-*4/"
print("Result:", evaluate_postfix(exp))
Output
Expression: 52+83-*4/
Infix: ((5+2)*(8-3))/4
Result: 8
🧠 Real-World Use Case of Expression Parsing
- Compilers convert human-readable code to machine instructions.
- Calculators and math evaluation engines.
- Spreadsheets like Excel use postfix to calculate complex cell formulas.
- Game engines (scripting expressions).
✅ Prefix Expression Evaluation
🔶 What is a Prefix Expression?
In Prefix (Polish Notation), operators come before their operands.
Example:
+ 9 * 2 3 → 9 + (2 * 3)
📜 Algorithm: Prefix Evaluation
We evaluate a prefix expression from right to left.
- Initialize an empty stack.
- Traverse the expression from right to left:
- If operand: push to stack.
- If operator: pop two elements, apply the operator, push the result.
- Final result is the only element in the stack.
🖥️ Implementations in C, C++, Java, Python Languages
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <string.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int val) {
stack[++top] = val;
}
int pop() {
return stack[top--];
}
int evaluatePrefix(char* exp) {
int len = strlen(exp);
for (int i = len - 1; i >= 0; i--) {
if (isdigit(exp[i])) {
push(exp[i] - '0');
} else {
int op1 = pop();
int op2 = pop();
switch (exp[i]) {
case '+': push(op1 + op2); break;
case '-': push(op1 - op2); break;
case '*': push(op1 * op2); break;
case '/': push(op1 / op2); break;
case '^': push(pow(op1, op2)); break;
}
}
}
return pop();
}
int main() {
char exp[] = "-+7*45+20";
printf("Result: %d\n", evaluatePrefix(exp));
return 0;
}
Output
For expression:
- + 7 * 4 5 + 2 0
Evaluation:
= (7 + (4 * 5)) - (2 + 0)
= (7 + 20) - 2
= 25
Result: 25
#include <iostream>
#include <stack>
#include <cmath>
using namespace std;
int evaluate(string exp) {
stack<int> s;
for (int i = exp.length() - 1; i >= 0; i--) {
char ch = exp[i];
if (isdigit(ch)) {
s.push(ch - '0');
} else {
int a = s.top(); s.pop();
int b = s.top(); s.pop();
switch (ch) {
case '+': s.push(a + b); break;
case '-': s.push(a - b); break;
case '*': s.push(a * b); break;
case '/': s.push(a / b); break;
case '^': s.push(pow(a, b)); break;
}
}
}
return s.top();
}
int main() {
string exp = "-+7*45+20";
cout << "Result: " << evaluate(exp) << endl;
return 0;
}
Output
For expression:
- + 7 * 4 5 + 2 0
Evaluation:
= (7 + (4 * 5)) - (2 + 0)
= (7 + 20) - 2
= 25
Result: 25
import java.util.*;
public class PrefixEval {
public static int evaluate(String exp) {
Stack<Integer> stack = new Stack<>();
for (int i = exp.length() - 1; i >= 0; i--) {
char ch = exp.charAt(i);
if (Character.isDigit(ch)) {
stack.push(ch - '0');
} else {
int op1 = stack.pop();
int op2 = stack.pop();
switch (ch) {
case '+': stack.push(op1 + op2); break;
case '-': stack.push(op1 - op2); break;
case '*': stack.push(op1 * op2); break;
case '/': stack.push(op1 / op2); break;
case '^': stack.push((int)Math.pow(op1, op2)); break;
}
}
}
return stack.pop();
}
public static void main(String[] args) {
String exp = "-+7*45+20";
System.out.println("Result: " + evaluate(exp));
}
}
Output
For expression:
- + 7 * 4 5 + 2 0
Evaluation:
= (7 + (4 * 5)) - (2 + 0)
= (7 + 20) - 2
= 25
Result: 25
def evaluate_prefix(expression):
stack = []
for ch in reversed(expression):
if ch.isdigit():
stack.append(int(ch))
else:
a = stack.pop()
b = stack.pop()
if ch == '+': stack.append(a + b)
elif ch == '-': stack.append(a - b)
elif ch == '*': stack.append(a * b)
elif ch == '/': stack.append(a // b)
elif ch == '^': stack.append(a ** b)
return stack[0]
exp = "-+7*45+20"
print("Result:", evaluate_prefix(exp))
Output
For expression:
- + 7 * 4 5 + 2 0
Evaluation:
= (7 + (4 * 5)) - (2 + 0)
= (7 + 20) - 2
= 25
Result: 25
💡 Real-World Applications
- Expression evaluators in compilers and calculators.
- Abstract syntax tree processing.
- Robotics (interpreting movement expressions).
- Embedded devices with limited parsing capabilities.
🧮 Stack-Based Expression Parsing in Real Calculators
Modern calculators (and programming languages) use stacks to handle complex expressions — especially those with multiple operators and nested parentheses.
🔄 Why Use a Stack?
Stacks follow the Last-In-First-Out (LIFO) principle. This is perfect for:
- Keeping track of operands and operators during parsing.
- Managing operator precedence and associativity.
- Handling parentheses
🧠 Real Example:
Infix Expression: 3 + 4 * (2 - 1)
To evaluate this in a calculator, it's typically converted to Postfix (Reverse Polish Notation):
3 4 2 1 - * +
Then it’s evaluated using a stack:
- Push operands onto stack: [3], then [3, 4], then [3, 4, 2], etc.
- When an operator is found, pop operands, apply the operator, and push result back.
📚 Step-by-Step (Postfix Evaluation)
Expression: 3 4 2 1 - * +
| Step | Stack | Action |
|---|---|---|
|
1 |
3 |
Push 3 |
|
2 |
3 4 |
Push 4 |
|
3 |
3 4 2 |
Push 2 |
|
4 |
3 4 2 1 |
Push 1 |
|
5 |
3 4 1 |
2 - 1 = 1 |
|
6 |
3 4 |
Replace with result 1 |
|
7 |
3 4 * 1 |
4 * 1 = 4 |
|
8 |
3 |
Replace with 4 |
|
9 |
3 + 4 = 7 |
Final result = 7 |
✅ How It's Implemented in Real Calculators
🛠 Internally:
- Converts infix expressions to postfix (using Shunting Yard algorithm by Dijkstra).
- Uses two stacks:
- One for operands (numbers).
- One for operators (+, -, *, /, (, )).
🔄 Expression Evaluation Phases:
- Lexical Analysis: Break input into tokens (numbers, operators).
- Conversion to Postfix: Apply precedence and associativity.
- Evaluation: Use a stack to compute result.
Postfix Evaluation - Code Example in C, C++, Java, Python
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int val) { stack[++top] = val; }
int pop() { return stack[top--]; }
int evaluatePostfix(char* exp) {
for (int i = 0; exp[i]; i++) {
if (isdigit(exp[i]))
push(exp[i] - '0');
else {
int b = pop(), a = pop();
switch (exp[i]) {
case '+': push(a + b); break;
case '-': push(a - b); break;
case '*': push(a * b); break;
case '/': push(a / b); break;
}
}
}
return pop();
}
int main() {
char postfix[] = "3421-*+";
printf("Result: %d\n", evaluatePostfix(postfix));
return 0;
}
Output
Result: 7
#include <iostream>
#include <stack>
#include <cctype>
using namespace std;
int evaluatePostfix(string exp) {
stack<int> s;
for (char ch : exp) {
if (isdigit(ch)) {
s.push(ch - '0');
} else {
int val2 = s.top(); s.pop();
int val1 = s.top(); s.pop();
switch (ch) {
case '+': s.push(val1 + val2); break;
case '-': s.push(val1 - val2); break;
case '*': s.push(val1 * val2); break;
case '/': s.push(val1 / val2); break;
}
}
}
return s.top();
}
int main() {
string exp = "3421-*+";
cout << "Result: " << evaluatePostfix(exp) << endl;
}
Output
Result: 7
import java.util.Stack;
public class Calculator {
public static int evaluatePostfix(String exp) {
Stack<Integer> stack = new Stack<>();
for (char ch : exp.toCharArray()) {
if (Character.isDigit(ch)) {
stack.push(ch - '0');
} else {
int b = stack.pop();
int a = stack.pop();
switch (ch) {
case '+': stack.push(a + b); break;
case '-': stack.push(a - b); break;
case '*': stack.push(a * b); break;
case '/': stack.push(a / b); break;
}
}
}
return stack.pop();
}
public static void main(String[] args) {
String postfix = "3421-*+";
System.out.println("Result: " + evaluatePostfix(postfix));
}
}
Output
Result: 7
def evaluate_postfix(expr):
stack = []
for ch in expr:
if ch.isdigit():
stack.append(int(ch))
else:
b = stack.pop()
a = stack.pop()
if ch == '+':
stack.append(a + b)
elif ch == '-':
stack.append(a - b)
elif ch == '*':
stack.append(a * b)
elif ch == '/':
stack.append(a // b)
return stack[0]
postfix = "3421-*+"
print("Result:", evaluate_postfix(postfix))
Output
Result: 7