Converting a Fully Parenthesized Infix expression into Postfix expression
Analysis:
Five types of input characters- Opening parentheses
- Operands
- Operators
- Closing parentheses
- New line character (\n)
Pseudocode:
********************************************************
Function : main
Calls : createStack
freeStack
pushIntoStack
popFromStack
Called by : NONE
Input
Parameters: Accepts input expression for processing
Returns : Converts Fully paranthesized INFIX
expression into POSTFIX expression
********************************************************
SET i to 0
GET infix expression from user into input_array
SET var with input_array[i]
CALL createStack
WHILE var != end of string
IF var equals to '(' THEN
CALL pushIntoStack (stack, var)
ELSE IF var is a number THEN
PRINT var
ELSE IF var is an arithmetic operator THEN
CALL pushIntoStack (stack, var)
ELSE IF var equals to ')' THEN
WHILE stackTop != '('
IF stackTop is an arithmetic operator THEN
PRINT stackTop
popFromStack (stack)
ENDIF
ENDWHILE
popFromStack (stack)
ENDIF
SET var with input_expression[INCREMENT i]
ENDWHILE
CALL freeStack (stack)
Complexity:
- Time Complexity: O(n)
- Space Complexity: O(n)
Explanation:
We will try out above pseudocode with input expression - (((8+1)-(7-4))/(11-9))
Input
|
Operation
|
Stack
(after op)
|
Output
on monitor
|
(
|
Push
operand into stack
|
(
|
|
(
|
Push
operand into stack
|
(
(
|
|
(
|
Push
operand into stack
|
(
( (
|
|
8
|
Print
it
|
8
|
|
+
|
Push
operator into stack
|
(
( ( +
|
8
|
1
|
Print
it
|
8
1
|
|
)
|
Pop
from the stack: Since popped element is '+' print it
|
(
( (
|
8
1 +
|
Pop
from the stack: Since popped element is '(' we ignore it and read next
character
|
(
(
|
8
1 +
|
|
-
|
Push
operator into stack
|
(
( -
|
|
(
|
Push
operand into stack
|
(
( - (
|
|
7
|
Print
it
|
8
1 + 7
|
|
-
|
Push
the operator in the stack
|
(
( - ( -
|
|
4
|
Print
it
|
8
1 + 7 4
|
|
)
|
Pop
from the stack: Since popped element is '-' print it
|
(
( - (
|
8
1 + 7 4 -
|
Pop
from the stack: Since popped element is '(' we ignore it and read next
character
|
(
( -
|
||
)
|
Pop
from the stack: Since popped element is '-' print it
|
(
(
|
8
1 + 7 4 - -
|
Pop
from the stack: Since popped element is '(' we ignore it and read next
character
|
(
|
||
/
|
Push
the operand into the stack
|
(
/
|
|
(
|
Push
into the stack
|
(
/ (
|
|
11
|
Print
it
|
8
1 + 7 4 - - 11
|
|
-
|
Push
the operand into the stack
|
(
/ ( -
|
|
9
|
Print
it
|
8
1 + 7 4 - - 11 9
|
|
)
|
Pop
from the stack: Since popped element is '-' print it
|
(
/ (
|
8
1 + 7 4 - - 11 9 -
|
Pop
from the stack: Since popped element is '(' we ignore it and read next
character
|
(
/
|
||
)
|
Pop
from the stack: Since popped element is '/' print it
|
(
|
8
1 + 7 4 - - 11 9 - /
|
Pop
from the stack: Since popped element is '(' we ignore it and read next
character
|
Stack
is empty
|
||
New
line character
|
STOP
|
Sample Code:
stack01.h
#define MAX_ARRAY_SIZE 50
#define MAX_STACK_SIZE 10
#define RESULT_ERROR -1
#define RESULT_OK 0
struct sllNode
{
struct sllNode *next;
char data;
};
struct sllHead
{
struct sllNode *next;
u_int32_t count;
u_int32_t maxStackSize;
};
#define IS_ARITHMETIC_OPERATOR(_i)
((_i == '*') || (_i == '+') || (_i == '-') || (_i == '/') || (_i == '%'))
#define IS_OPERAND(_i)
( (_i >= '0' && _i <= '9') ||
(_i >= 'a' && _i <= 'z') ||
(_i >= 'A' && _i <= 'Z'))
#define IS_STACK_EMPTY(_stack) ((_stack) ? _stack->count : 0)
#define STACK_TOP(_stack) ((_stack) ?
((_stack->next) ?
(_stack->next->data) : 0) : 0)
stack01.c /*FULLY PARANTHESIZED INFIX to POSTFIX*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack01.h"
/*Poping from a Stack*/
int popFromStack(struct sllHead *head)
{
struct sllNode *tmpNode_ptr = NULL;
if (!head)
{
return RESULT_ERROR;
}
if (head->next)
{
tmpNode_ptr = head->next;
head->next = head->next->next;
free(tmpNode_ptr);
head->count--;
}
else
printf("Stack is Emptyn");
return RESULT_OK;
}
/*Pushing into Stack*/
int pushIntoStack(struct sllHead *head, char data)
{
struct sllNode *tmpNode_ptr = NULL;
if (!head)
{
return RESULT_ERROR;
}
if (head->count == head->maxStackSize)
{
printf ("Stack is FILLED to MAX leveln");
return RESULT_ERROR;
}
tmpNode_ptr = (struct sllNode *)calloc(1, sizeof(struct sllNode));
if (tmpNode_ptr)
tmpNode_ptr->data = data;
else
{
printf("Memory Allocation Failedn");
return RESULT_ERROR;
}
tmpNode_ptr->next = head->next;
head->next = tmpNode_ptr;
head->count++;
return RESULT_OK;
}
struct sllHead * createStack()
{
struct sllHead *head = NULL;
head = (struct sllHead *)calloc(1, sizeof(struct sllHead));
if (head)
head->maxStackSize = MAX_STACK_SIZE;
return head;
}
void freeStack(struct sllHead **head)
{
if (*head)
{
while((*head)->count)
popFromStack(*head);
free(*head);
*head = NULL;
}
}
int main(int argc, char *argv[])
{
char in[MAX_ARRAY_SIZE];
short i = 0;
struct sllHead *stack;
u_char operand_before = 0;
memset(in, 0, MAX_ARRAY_SIZE);
printf("Enter INFIX expression : ");
scanf("%s", in);
stack = createStack();
while(i < MAX_ARRAY_SIZE && in[i] != '\0')
{
if (in[i] == '(' ||
IS_ARITHMETIC_OPERATOR(in[i]))
{
pushIntoStack (stack,in[i]);
operand_before = 0;
}
else if (IS_OPERAND(in[i]))
{
if (operand_before)
printf ("%c", in[i]);
else
printf (" %c", in[i]);
operand_before = 1;
}
else if (in[i] == ')')
{
operand_before = 0;
while (IS_STACK_EMPTY(stack) &&
STACK_TOP(stack) != '(')
{
if (IS_ARITHMETIC_OPERATOR(STACK_TOP(stack)))
{
printf(" %c", STACK_TOP(stack));
popFromStack(stack);
}
}
if (STACK_TOP(stack) == '(')
popFromStack(stack);
}
i++;
}
printf ("\n");
EXIT:
freeStack (&stack);
return RESULT_OK;
}
No comments :
Post a Comment
Your comments are moderated