[go: up one dir, main page]
Scribd
Upload
9 views3 pages

DSU2

fj

Uploaded by

Shruti Pednekar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
9 views3 pages

DSU2

fj

Uploaded by

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

#include<stdio.

h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
struct Stack {
int top;
int maxSize;
int* array;
};
struct Stack* create(int max)
{
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->maxSize = max;
stack->top = -1;
stack->array = (int*)malloc(stack->maxSize * sizeof(int));
return stack;
}
int isFull(struct Stack* stack)
{
if(stack->top == stack->maxSize - 1){
printf("Will not be able to push maxSize reached\n");
}
return stack->top == stack->maxSize - 1;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
void push(struct Stack* stack, int item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
}
int pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top--];
}
int peek(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top];
}
int checkIfOperand(char ch)
{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
int precedence(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
int covertInfixToPostfix(char* expression)
{
int i, j;
struct Stack* stack = create(strlen(expression));
if(!stack) // just checking is stack was created or not
return -1 ;
for (i = 0, j = -1; expression[i]; ++i)
{
if (checkIfOperand(expression[i]))
expression[++j] = expression[i];
else if (expression[i] == '(')
push(stack, expression[i]);
else if (expression[i] == ')')
{
while (!isEmpty(stack) && peek(stack) != '(')
expression[++j] = pop(stack);
if (!isEmpty(stack) && peek(stack) != '(')
return -1; // invalid expression
else
pop(stack);
}
else // if an opertor
{
while (!isEmpty(stack) && precedence(expression[i]) <= precedence(peek(stack)))
expression[++j] = pop(stack);
push(stack, expression[i]);
}
}
while (!isEmpty(stack))
expression[++j] = pop(stack);
expression[++j] = '\0';
printf( "%s", expression);
}
int main()
{
char expression[] = "((p+(q*r))-s)";
covertInfixToPostfix(expression);
return 0;
}

You might also like