Dsa Expt 8 123a3007

DSA EXPT 8 NAME- SIDDHESH BAGDE PRN : 123A3007
1. Infix to Postfix Conversion

In an infix expression, operators are written between the
operands (e.g., A + B). This is the most common form for
mathematical expressions but is harder for computers to evaluate
directly. Postfix expressions, on the other hand, place operators
after their operands (e.g., A B +), making them easier to evaluate
using a stack.
Algorithm to Convert Infix to Postfix:
• Step 1: Initialize an empty stack for operators and an empty
list for the postfix expression.
• Step 2: Scan the infix expression from left to right.
o Operand: If the character is an operand, append it to
the postfix list.
o Left Parenthesis ((): Push it to the stack.
o Right Parenthesis ()): Pop from the stack until a left
parenthesis is encountered, appending the popped
operators to the postfix list.
o Operator: If the character is an operator, pop operators
from the stack to the postfix list as long as the top of
the stack has the same or higher precedence. Then
push the current operator to the stack.
• Step 3: After scanning the expression, pop any remaining
operators from the stack and append them to the postfix list.
Example:
• For the infix expression: A + B * (C - D)
The postfix expression will be: A B C D - * +
2. Evaluation of Postfix Expression

Once you have a postfix expression, you can evaluate it efficiently
using a stack.
Algorithm for Postfix Evaluation:
• Step 1: Initialize an empty stack.
• Step 2: Scan the postfix expression from left to right.
o Operand: Push it to the stack.
o Operator: Pop the required number of operands from
the stack, apply the operator, and push the result back
onto the stack.
• Step 3: After scanning the expression, the result of the
expression will be on the top of the stack.
Example:
For the postfix expression: A B C D - * + (Assume A=5, B=3, C=8,
D=2)
1. Push 5 (A) onto the stack.
2. Push 3 (B) onto the stack.
3. Push 8 (C) onto the stack.
4. Push 2 (D) onto the stack.
5. Apply - to C and D: 8 - 2 = 6. Push the result (6) onto the
stack.
6. Apply * to B and the result of C - D: 3 * 6 = 18. Push the result
(18) onto the stack.
7. Apply + to A and the result of B * (C - D): 5 + 18 = 23. Push the

result (23) onto the stack.
Final result : 23.
Data Structure Used: Stack

The stack is the most appropriate data structure for these tasks
because it allows easy handling of operators and operands in the
correct order. The LIFO (Last In First Out) nature of a stack
ensures that operators are processed in the reverse order of their
insertion, which is necessary for postfix evaluation.
Key Concepts:
• Operator Precedence: Ensure that operators are applied in
the correct order of precedence.
• Associativity: Handle cases where two operators of the
same precedence appear next to each other (like * and /).
Code :
#include <stdio.h>
#include <ctype.h> // For isdigit()
#include <string.h>
#define MAX 100
// Stack structure
char stack[MAX];
int top = -1;
// Stack operations
void push(char x) {
if (top == MAX - 1) {
printf("Stack Overflow\n");
} else {
stack[++top] = x;
char pop() {
if (top == -1) {
printf("Stack Underflow\n");
return -1;
} else {
return stack[top--];
// Function to return precedence of operators
int precedence(char x) {
if (x == '+' || x == '-') {
return 1; // Lower precedence
} else if (x == '*' || x == '/') {
return 2; // Higher precedence
return 0; // Non-operator
// Infix to Postfix Conversion
void infixToPostfix(char infix[], char postfix[]) {
int i = 0, j = 0;
char ch;
while (infix[i] != '\0') {
ch = infix[i];
// If operand, add to postfix
if (isalnum(ch)) {
postfix[j++] = ch;
// If '(', push to stack
else if (ch == '(') {
push(ch);
// If ')', pop until '('
else if (ch == ')') {
while (stack[top] != '(') {
postfix[j++] = pop();
pop(); // Remove '('
// If operator, pop according to precedence
else {
while (top != -1 && precedence(stack[top]) >= precedence(ch)) {

push(ch);
i++;
// Pop remaining operators
while (top != -1) {
postfix[j] = '\0'; // Null-terminate the postfix expression
// Function to evaluate a postfix expression
int evaluatePostfix(char postfix[]) {
int stack[MAX];
int top = -1;
int i = 0;
char ch;
while (postfix[i] != '\0') {
ch = postfix[i];
// If operand, push to stack
if (isdigit(ch)) {
stack[++top] = ch - '0'; // Convert char to integer

// If operator, pop two operands and apply operator
else {
int val2 = stack[top--];
int val1 = stack[top--];
switch (ch) {
case '+': stack[++top] = val1 + val2; break;
case '-': stack[++top] = val1 - val2; break;
case '*': stack[++top] = val1 * val2; break;
case '/': stack[++top] = val1 / val2; break;
i++;
return stack[top]; // The result is the last element in the stack
int main() {
char infix[MAX], postfix[MAX];
// Input example: 3+4*(5-2)
printf("Enter an infix expression: ");
scanf("%s", infix);
// Convert infix to postfix

infixToPostfix(infix, postfix);
printf("Postfix Expression: %s\n", postfix);
// Evaluate the postfix expression
int result = evaluatePostfix(postfix);
printf("Result of evaluation: %d\n", result);
return 0;
Output :
Enter an infix expression: A+B*(C-D)
Postfix Expression: ABCD-*+
Result of evaluation: 0
=== Code Execution Successful ===

Dsa Expt 8 123a3007

Uploaded by

Copyright:

Available Formats

Dsa Expt 8 123a3007

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Dsa Expt 8 123a3007

Uploaded by

Copyright:

Available Formats

DSA EXPT 8 NAME- SIDDHESH BAGDE PRN : 123A3007

1. Infix to Postfix Conversion

2. Evaluation of Postfix Expression

7. Apply + to A and the result of B * (C - D): 5 + 18 = 23. Push the

Final result : 23.

Data Structure Used: Stack

#include <ctype.h> // For isdigit()

#define MAX 100

int top = -1;

// Function to return precedence of operators

return 1; // Lower precedence

} else if (x == '*' || x == '/') {

return 2; // Higher precedence

// Infix to Postfix Conversion

void infixToPostfix(char infix[], char postfix[]) {

while (infix[i] != '\0') {

// If operand, add to postfix

// If '(', push to stack

else if (ch == '(') {

// If ')', pop until '('

else if (ch == ')') {

while (stack[top] != '(') {

pop(); // Remove '('

// If operator, pop according to precedence

while (top != -1 && precedence(stack[top]) >= precedence(ch)) {

// Pop remaining operators

while (top != -1) {

postfix[j] = '\0'; // Null-terminate the postfix expression

// Function to evaluate a postfix expression

int evaluatePostfix(char postfix[]) {

int top = -1;

while (postfix[i] != '\0') {

// If operand, push to stack

stack[++top] = ch - '0'; // Convert char to integer

// If operator, pop two operands and apply operator

int val2 = stack[top--];

int val1 = stack[top--];

case '+': stack[++top] = val1 + val2; break;

case '-': stack[++top] = val1 - val2; break;

case '*': stack[++top] = val1 * val2; break;

case '/': stack[++top] = val1 / val2; break;

return stack[top]; // The result is the last element in the stack

char infix[MAX], postfix[MAX];

// Input example: 3+4*(5-2)

printf("Enter an infix expression: ");

// Convert infix to postfix

printf("Postfix Expression: %s\n", postfix);

// Evaluate the postfix expression

int result = evaluatePostfix(postfix);

printf("Result of evaluation: %d\n", result);

Postfix Expression: ABCD-*+

=== Code Execution Successful ===

You might also like

case '': stack[++top] = val1 val2; break;