DSA
Name : Atul Sharma
Roll No. :GF202454368
Subject : DSA
Submitted to : Mr. Rishi Sir
Class : B.tech cse Data Science(G4)
Assignment: Expression Evaluation in Infix, Prefix, and Postfix Notation
Theory
1. Infix Expression
● Operators are placed between operands.
● Example: (A + B) * (C - D)
● Requires parentheses and operator precedence to evaluate.
2. Prefix Expression (Polish Notation)
● Operators are placed before operands.
● Example: * + A B - C D
● No need for parentheses; evaluation is unambiguous.
3. Postfix Expression (Reverse Polish Notation)
● Operators come after operands.
● Example: A B + C D - *
● Evaluated using a stack, from left to right.
Part B: Expression Conversion Example
Given:
Infix: (A + B) * (C - D)
Conversions:
● Prefix: * + A B - C D
● Postfix: A B + C D - *
Postfix Evaluation Using C++
#include <iostream>
#include <stack>
#include <cctype>
using namespace std;
int evaluatePostfix(string exp) {
stack<int> s;
for (char c : exp) {
if (isdigit(c)) {
s.push(c - '0'); // Convert char to int
} else {
int val2 = s.top(); s.pop();
int val1 = s.top(); s.pop();
switch (c) {
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 postfix = "52+83-*"; // (5+2)*(8-3)
cout << "Result: " << evaluatePostfix(postfix) << endl;
return 0;
}
Output:
Result: 35
Prefix Evaluation Using C++
#include <iostream>
#include <stack>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
int evaluatePrefix(string exp) {
stack<int> st;
reverse(exp.begin(), exp.end()); // Reverse the string for prefix evaluation
for (char c : exp) {
if (isdigit(c)) {
st.push(c - '0'); // Convert char to int (assuming single-digit operands)
} else {
int val1 = st.top(); st.pop();
int val2 = st.top(); st.pop();
switch(c) {
case '+': st.push(val1 + val2); break;
case '-': st.push(val1 - val2); break;
case '*': st.push(val1 * val2); break;
case '/': st.push(val1 / val2); break;
case '^': st.push(pow(val1, val2)); break;
}
}
}
return st.top();
}
int main() {
string prefix = "-*+52 83"; // equivalent to (5+2)*(8-3)
cout << "Result: " << evaluatePrefix(prefix) << endl;
return 0;
}
Output:
Result: 35
Infix Evaluation Using C++
#include <iostream>
#include <stack>
#include <string>
#include <cctype>
#include <cmath>
using namespace std;
int precedence(char op) {
if (op == '^') return 3;
else if (op == '*' || op == '/') return 2;
else if (op == '+' || op == '-') return 1;
else return -1;
}
int applyOperator(int a, int b, char op) {
switch(op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
case '^': return pow(a, b);
default: return 0;
}
}
int evaluateInfix(string expression) {
stack<int> values;
stack<char> ops;
for (int i = 0; i < expression.length(); i++) {
char c = expression[i];
if (c == ' ') continue;
if (isdigit(c)) {
int value = 0;
while (i < expression.length() && isdigit(expression[i])) {
value = (value * 10) + (expression[i] - '0');
i++;
}
i--;
values.push(value);
}
else if (c == '(') {
ops.push(c);
}
else if (c == ')') {
while (!ops.empty() && ops.top() != '(') {
int val2 = values.top(); values.pop();
int val1 = values.top(); values.pop();
char op = ops.top(); ops.pop();
values.push(applyOperator(val1, val2, op));
}
ops.pop();
}
else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^') {
while (!ops.empty() && precedence(ops.top()) >= precedence(c)) {
int val2 = values.top(); values.pop();
int val1 = values.top(); values.pop();
char op = ops.top(); ops.pop();
values.push(applyOperator(val1, val2, op));
}
ops.push(c);
}
}
while (!ops.empty()) {
int val2 = values.top(); values.pop();
int val1 = values.top(); values.pop();
char op = ops.top(); ops.pop();
values.push(applyOperator(val1, val2, op));
}
return values.top();
}
int main() {
string infix = "(3+5)*2-(8/4)^2";
cout << "Result: " << evaluateInfix(infix) << endl;
return 0;
}
Output:
Result: 12
