Infix to prefix and evaluate prefix expression

Write a C Program to convert infix to prefix using stack and evaluate prefix expression. Here’s simple Program to convert infix to prefix using stack and evaluate prefix expression in C Programming Language.

What is Stack ?

Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack, the only element that can be removed is the element that was at the top of the stack, just like a pile of objects.

Basic Operations : :

push() − Pushing (storing) an element on the stack.

pop() − Removing (accessing) an element from the stack.

peek() − get the top data element of the stack, without removing it.

isFull() − check if stack is full.

isEmpty() − check if stack is empty.

Below is the source code for C Program to convert infix to prefix using stack and evaluate prefix expression which is successfully compiled and run on Windows System to produce desired output as shown below :

SOURCE CODE : :

/*  C Program to convert infix to prefix and evaluate prefix expression  */

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>

#define BLANK ' '
#define TAB '\t'
#define MAX 50

long int pop();
long int eval_pre();
char infix[MAX], prefix[MAX];
long int stack[MAX];
int top;
int isempty();
int white_space(char symbol);

void infix_to_prefix();
int priority(char symbol);
void push(long int symbol);
long int pop();
long int eval_pre();

int main()
{
        long int value;
        top = -1;
        printf("Enter infix : ");
        gets(infix);
        infix_to_prefix();
        printf("prefix : %s\n",prefix);
        value=eval_pre();
        printf("Value of expression : %ld\n",value);

        return 0;

}/*End of main()*/

void infix_to_prefix()
{
        int i,j,p,n;
        char next ;
        char symbol;
        char temp;
        n=strlen(infix);
        p=0;

        for(i=n-1; i>=0; i--)
        {
                symbol=infix[i];
                if(!white_space(symbol))
                {
                        switch(symbol)
                        {
                        case ')':
                                push(symbol);
                                break;
                        case '(':
                                while( (next=pop()) != ')')
                                        prefix[p++] = next;
                                break;
                        case '+':
                        case '-':
                        case '*':
                        case '/':
                        case '%':
                        case '^':
                                while( !isempty( ) &&  priority(stack[top])> priority(symbol) )
                                        prefix[p++] = pop();
                                push(symbol);
                                break;
                        default: /*if an operand comes*/
                             prefix[p++] = symbol;
                        }
                }
        }
        while(!isempty( ))
                prefix[p++] = pop();
        prefix[p] = '\0'; /*End prefix with'\0' to make it a string*/

        for(i=0,j=p-1;i<j;i++,j--)
        {
                temp=prefix[i];
                prefix[i]=prefix[j];
                prefix[j]=temp;
        }
}/*End of infix_to_prefix()*/

/* This function returns the priority of the operator */
int priority(char symbol )
{
        switch(symbol)
        {
        case ')':
                return 0;
        case '+':
        case '-':
                return 1;
        case '*':
        case '/':
        case '%':
                return 2;
        case '^':
                return 3;
        default :
                 return 0;
        }/*End of switch*/
}/*End of priority()*/

void push(long int symbol)
{
        if(top > MAX)
        {
                printf("Stack overflow\n");
                exit(1);
        }
        else
        {
                top=top+1;
                stack[top] = symbol;
        }
}/*End of push()*/

long int pop()
{
        if(top == -1 )
        {
                printf("Stack underflow \n");
                exit(2);
        }
        return (stack[top--]);
}/*End of pop()*/
int isempty()
{
        if(top==-1)
                return 1;
        else
                return 0;
}

int white_space(char symbol)
{
        if(symbol==BLANK || symbol==TAB || symbol=='\0')
                return 1;
        else
                return 0;
}/*End of white_space()*/

long int eval_pre()
{
        long int a,b,temp,result;
        int i;

        for(i=strlen(prefix)-1;i>=0;i--)
        {
                if(prefix[i]<='9' && prefix[i]>='0')
                        push( prefix[i]-48 );
                else
                {
                        b=pop();
                        a=pop();
                        switch(prefix[i])
                        {
                        case '+':
                                temp=b+a; break;
                        case '-':
                                temp=b-a;break;
                        case '*':
                                temp=b*a;break;
                        case '/':
                                temp=b/a;break;
                        case '%':
                                temp=b%a;break;
                        case '^':
                                temp=pow(b,a);
                        }
                        push(temp);
                }
        }
        result=pop();
        return result;
}/*End of eval_pre */

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

/* C Program to convert infix to prefix and evaluate prefix expression */

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<stdlib.h>

#define BLANK ' '

#define TAB '\t'

#define MAX 50

long int pop();

long int eval_pre();

char infix[MAX], prefix[MAX];

long int stack[MAX];

int top;

int isempty();

int white_space(char symbol);

void infix_to_prefix();

int priority(char symbol);

void push(long int symbol);

long int pop();

long int eval_pre();

int main()

{

long int value;

top = -1;

printf("Enter infix : ");

gets(infix);

infix_to_prefix();

printf("prefix : %s\n",prefix);

value=eval_pre();

printf("Value of expression : %ld\n",value);

return 0;

}/*End of main()*/

void infix_to_prefix()

{

int i,j,p,n;

char next ;

char symbol;

char temp;

n=strlen(infix);

p=0;

for(i=n-1; i>=0; i--)

{

symbol=infix[i];

if(!white_space(symbol))

{

switch(symbol)

{

case ')':

push(symbol);

break;

case '(':

while( (next=pop()) != ')')

prefix[p++] = next;

break;

case '+':

case '-':

case '*':

case '/':

case '%':

case '^':

while( !isempty( ) && priority(stack[top])> priority(symbol) )

prefix[p++] = pop();

push(symbol);

break;

default: /*if an operand comes*/

prefix[p++] = symbol;

}

while(!isempty( ))

prefix[p++] = pop();

prefix[p] = '\0'; /*End prefix with'\0' to make it a string*/

for(i=0,j=p-1;i<j;i++,j--)

{

temp=prefix[i];

prefix[i]=prefix[j];

prefix[j]=temp;

}

}/*End of infix_to_prefix()*/

/* This function returns the priority of the operator */

int priority(char symbol )

{

switch(symbol)

{

case ')':

return 0;

case '+':

case '-':

return 1;

case '*':

case '/':

case '%':

return 2;

case '^':

return 3;

default :

return 0;

}/*End of switch*/

}/*End of priority()*/

void push(long int symbol)

{

if(top > MAX)

{

printf("Stack overflow\n");

exit(1);

}

else

{

top=top+1;

stack[top] = symbol;

}

}/*End of push()*/

long int pop()

{

if(top == -1 )

{

printf("Stack underflow \n");

exit(2);

}

return (stack[top--]);

}/*End of pop()*/

int isempty()

{

if(top==-1)

return 1;

else

return 0;

}

int white_space(char symbol)

{

if(symbol==BLANK || symbol==TAB || symbol=='\0')

return 1;

else

return 0;

}/*End of white_space()*/

long int eval_pre()

{

long int a,b,temp,result;

int i;

for(i=strlen(prefix)-1;i>=0;i--)

{

if(prefix[i]<='9' && prefix[i]>='0')

push( prefix[i]-48 );

else

{

b=pop();

a=pop();

switch(prefix[i])

{

case '+':

temp=b+a; break;

case '-':

temp=b-a;break;

case '*':

temp=b*a;break;

case '/':

temp=b/a;break;

case '%':

temp=b%a;break;

case '^':

temp=pow(b,a);

}

push(temp);

}

result=pop();

return result;

}/*End of eval_pre */

OUTPUT : :

/*  C Program to convert infix to prefix and evaluate prefix expression  */

-----------------------------------------------------------

Enter infix : A + B + C + D
prefix : +++ABCD
Stack underflow

------------------------------------------------------------

Enter infix : (9 + 8) * (5 + 6)
prefix : *+98+56
Value of expression : 187

Process returned 0

/* C Program to convert infix to prefix and evaluate prefix expression */

-----------------------------------------------------------

Enter infix : A + B + C + D

prefix : +++ABCD

Stack underflow

------------------------------------------------------------

Enter infix : (9 + 8) * (5 + 6)

prefix : *+98+56

Value of expression : 187

Process returned 0

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.

Thanks for reading the post….

5 2 votes

Article Rating