/* Ajith - Syntax Higlighter - End ----------------------------------------------- */

## 2.05.2013

### 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 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*/
{
struct sllNode *tmpNode_ptr = NULL;

{
return RESULT_ERROR;
}

{
free(tmpNode_ptr);
}
else
printf("Stack is Emptyn");

return RESULT_OK;
}

/*Pushing into Stack*/
{
struct sllNode *tmpNode_ptr = NULL;

{
return RESULT_ERROR;
}

{
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;
}

return RESULT_OK;
}

{

}

{
{

}
}

int main(int argc, char *argv[])
{
char in[MAX_ARRAY_SIZE];
short i = 0;
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;
}