[go: up one dir, main page]
Scribd
Upload
182 views6 pages

Scenario Based 3 (SIDHARTH K RA2011003010008)

The document describes an approach to evaluate postfix expressions using a stack. It defines a stack structure and functions to create, push, pop, and check if empty. The evaluatePostfixExpression function scans the expression string, pushing operands and evaluating operators by popping operands and pushing the result. It has linear time complexity O(n) and constant space complexity O(1).

Uploaded by

qwerty keypad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
182 views6 pages

Scenario Based 3 (SIDHARTH K RA2011003010008)

The document describes an approach to evaluate postfix expressions using a stack. It defines a stack structure and functions to create, push, pop, and check if empty. The evaluatePostfixExpression function scans the expression string, pushing operands and evaluating operators by popping operands and pushing the result. It has linear time complexity O(n) and constant space complexity O(1).

Uploaded by

qwerty keypad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

SCENARIO BASED SIDHARTH K

RA2011003010008
CSE A1
Question:
Given string S representing a postfix expression, the task is to evaluate the expression and
find the final value.

Approach:
Input is put into stack and each character is evaluated with switch case.

Scalability:
User inputs the desired data.

Code:
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

//declaring structure stack


struct Stack
{
int top;
int size;
int *array;
};

//Create stack
struct Stack *createStack(int size)
{
struct Stack *stack = (struct Stack *)malloc(sizeof(struct Stack));

if (!stack)
return NULL;

stack->top = -1;
stack->size = size;
stack->array = (int *)malloc(stack->size * sizeof(int));

if (!stack->array)
return NULL;

return stack;
}

//Checks if stack is empty


int isEmpty(struct Stack *stack)
{
return stack->top == -1;
}

//returns top value


char peek(struct Stack *stack)
{
return stack->array[stack->top];
}

//function to remove an element from stack


char pop(struct Stack *stack)
{
if (!isEmpty(stack))
return stack->array[stack->top--];
return '$';
}

//function to insert elements into stack


void push(struct Stack *stack, char op)
{
stack->array[++stack->top] = op;
}

// Evaluates postfix expression


int evaluatePostfixExpression(char *exp)
{
struct Stack *stack = createStack(strlen(exp));
int i;

// See if stack was created successfully


if (!stack)
return -1;

// Scans all characters one by one


for (i = 0; exp[i]; ++i)
{

if (isdigit(exp[i]))
push(stack, exp[i] - '0');
else
{
int val1 = pop(stack);
int val2 = pop(stack);
switch (exp[i])
{
case '+':
push(stack, val2 + val1);
break;
case '-':
push(stack, val2 - val1);
break;
case '*':
push(stack, val2 * val1);
break;
case '/':
push(stack, val2 / val1);
break;
}
}
}
return pop(stack);
}

int main()
{
char exp[10];
int n;
printf("Enter Total Test Cases\n");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%s", exp);
printf("EXPRESSION IN POSTFIX: %d\n", evaluatePostfixExpression(exp));
}
return 0;
}

Sample input output:


Dryrun:

Time and space complexity:


Time Complexity: O(n)
Space Complexity: O(1)

You might also like