#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// Stack type
struct Stack
{
int top;
unsigned capacity;
int* array;
};
// Stack Operations
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
if (!stack)
return NULL;
stack->top = -1;
stack->capacity = capacity;
stack->array = (int*)malloc(stack->capacity * sizeof(int));
if (!stack->array)
return NULL;
return stack;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
char peek(struct Stack* stack)
{
return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
if (!isEmpty(stack))
return stack->array[stack->top--];
return '$';
}
void push(struct Stack* stack, char op)
{
stack->array[++stack->top] = op;
}
int isOperand(char ch)
{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
int prec(char ch)
{
switch (ch)
{
case '+':
case '-' :
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
int infixToPostfix(char* exp)
{
int k , i ;
struct Stack* stack = createStack(strlen(exp));
if (!stack)
return -1;
for ( i = 0, k = -1; exp[i]; ++i)
{
//if scanned character is an operand , add to the output
if (isOperand(exp[i]))
exp[++k] = exp[i];
// If the scanned character is an ‘(‘, push it to the stack.
else if (exp[i] == '(')
push(stack, exp[i]);
// If the scanned character is an ‘)’, pop and output from the stack
// until an ‘(‘ is encountered.
else if (exp[i] == ')')
{
while (!isEmpty(stack) && peek(stack) != '(')
exp[++k] = pop(stack);
if (!isEmpty(stack) && peek(stack) != '(')
return -1; //invalid expression
else
pop(stack); // pop starting braces (
}
else //an operator is encountered
{
while (!isEmpty(stack) && prec(exp[i]) <= prec(peek(stack)))
exp[++k] = pop(stack);
push(stack, exp[i]);
}
}
// pop all the operators from the stack
while (!isEmpty(stack))
exp[++k] = pop(stack);
exp[++k] = '\0';
printf("%s\n", exp);
}
// Driver program to test above functions
int main()
{
char exp[] = "a+b*(c^d-e)^(f+g*h)-i";
infixToPostfix(exp);
getchar();
return 0;
}
#include <string.h>
#include <stdlib.h>
// Stack type
struct Stack
{
int top;
unsigned capacity;
int* array;
};
// Stack Operations
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
if (!stack)
return NULL;
stack->top = -1;
stack->capacity = capacity;
stack->array = (int*)malloc(stack->capacity * sizeof(int));
if (!stack->array)
return NULL;
return stack;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
char peek(struct Stack* stack)
{
return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
if (!isEmpty(stack))
return stack->array[stack->top--];
return '$';
}
void push(struct Stack* stack, char op)
{
stack->array[++stack->top] = op;
}
int isOperand(char ch)
{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
int prec(char ch)
{
switch (ch)
{
case '+':
case '-' :
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
int infixToPostfix(char* exp)
{
int k , i ;
struct Stack* stack = createStack(strlen(exp));
if (!stack)
return -1;
for ( i = 0, k = -1; exp[i]; ++i)
{
//if scanned character is an operand , add to the output
if (isOperand(exp[i]))
exp[++k] = exp[i];
// If the scanned character is an ‘(‘, push it to the stack.
else if (exp[i] == '(')
push(stack, exp[i]);
// If the scanned character is an ‘)’, pop and output from the stack
// until an ‘(‘ is encountered.
else if (exp[i] == ')')
{
while (!isEmpty(stack) && peek(stack) != '(')
exp[++k] = pop(stack);
if (!isEmpty(stack) && peek(stack) != '(')
return -1; //invalid expression
else
pop(stack); // pop starting braces (
}
else //an operator is encountered
{
while (!isEmpty(stack) && prec(exp[i]) <= prec(peek(stack)))
exp[++k] = pop(stack);
push(stack, exp[i]);
}
}
// pop all the operators from the stack
while (!isEmpty(stack))
exp[++k] = pop(stack);
exp[++k] = '\0';
printf("%s\n", exp);
}
// Driver program to test above functions
int main()
{
char exp[] = "a+b*(c^d-e)^(f+g*h)-i";
infixToPostfix(exp);
getchar();
return 0;
}
No comments:
Post a Comment