postfix / infix notation

alpesh · **Posted:** Sat Oct 02, 2004 10:24 am

// Turbo c++

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

char stack[50],y;
float stack1[50],z;
int top=-1,top1=-1,prec1=0,prec2=0;

int check(char value) /* sets precedence for the operator */
{
int prec=0;
switch(value)
{
case '+' : prec=1;break;
case '-' : prec=1;break;
case '*' : prec=2;break;
case '/' : prec=2;break;
case '^' : prec=3;break;
default : prec=0;
}
return(prec);
}
void push(char x)
{
top++;
stack[top]=x;
}
char pop()
{
y=stack[top];
top--;
return(y);
}
void push1(float x)
{
top1++;
stack1[top1]=x;
}
float pop1()
{
z=stack1[top1];
top1--;
return(z);
}
void main(void)
{
char tempa[1],infix[50],postfix[50];
int i=0,j=0,n,b=0,postfix1[50];
float af,bf,answer;
clrscr();
/* reading in the expression */
printf("ENTER THE EXPRESSION TO BE EVALUATED : ");
scanf("%s",infix);
i=strlen(infix);
push('(');
infix[i]=')';
n=i;
/* conversion to postfix */
for (i=0;i<=n;i++)
{
if ((infix[i]>='0') && (infix[i]<='9'))
{
postfix[j]=infix[i];
j++;
}
else if (infix[i]=='(')
{
push(infix[i]);
b++;
}
else if (infix[i]==')')
{
b++;
while (stack[top]!='(')
{
y=pop();
postfix[j]=y;
j++;
}
y=pop();
}
else
{
prec1=check(infix[i]);
prec2=4;
while (stack[top]!='(' && prec2>=prec1)
{
prec2=check(stack[top]);
if (prec2>=prec1)
{
postfix[j]=pop();
j++;
}
}
push(infix[i]);
}
}
n=n-b+1;
printf("\n%s","THE EQUIVALENT POSTFIX EXPRESSION IS : ");
for (i=0;i<n;i++)
printf("%c ",postfix[i]);
printf("\n\n");
/* evaluation of the postfix expression */
for (i=0;i<n;i++)
{
tempa[0]=postfix[i];
j=atoi(tempa);
postfix1[i]=j;
}
answer=0;
top1=-1;
for (i=0;i<n;i++)
{
if (postfix[i]>='0' && postfix[i]<='9')
push1(postfix1[i]);
else
{
bf=pop1();
af=pop1();
switch(postfix[i])
{
case '+' : answer=af+bf;break;
case '-' : answer=af-bf;break;
case '*' : answer=af*bf;break;
case '/' : answer=af/bf;break;
case '^' : answer=pow(af,bf);break;
}
push1(answer);
}
}
printf("%s %f","THE VALUE OF THE EXPRESSION ENTERED IS :",answer);
getch();
}

Wink

wtd · **Posted:** Sat Oct 02, 2004 1:07 pm

Where to begin?

If it seems like I'm beingcritical, then it's only because I like to correct bad habits where I see them, ad you have to expect some constructive criticism if you post in submissions, where high-quality code is to be expected.

Use code tags to maintain formatting of your code. I've also added spaces and indenting so that the code approaches readability.

code:

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

char stack[50], y;
float stack1[50], z;
int top = -1, top1 = -1, prec1 = 0, prec2 = 0;

int check(char value) /* sets precedence for the operator */
{
int prec = 0;

switch(value)
{
case '+':
prec = 1;
break;
case '-':
prec = 1;
break;
case '*':
prec = 2;
break;
case '/':
prec = 2;
break;
case '^':
prec = 3;
break;
default :
prec = 0;
}

return(prec);
}

void push(char x)
{
top++;
stack[top] = x;
}

char pop()
{
y = stack[top];
top--;
return(y);
}

void push1(float x)
{
top1++;
stack1[top1] = x;
}

float pop1()
{
z = stack1[top1];
top1--;
return(z);
}

void main(void)
{
char tempa[1], infix[50], postfix[50];
int i = 0,j = 0, n, b = 0, postfix1[50];
float af, bf, answer;

clrscr();

/* reading in the expression */
printf("ENTER THE EXPRESSION TO BE EVALUATED : ");
scanf("%s", infix);

i = strlen(infix);
push('(');
infix[i] = ')';
n = i;

/* conversion to postfix */
for (i = 0; i <= n; i++)
{
if ((infix[i] >= '0') && (infix[i] <= '9'))
{
postfix[j] = infix[i];
j++;
}
else if (infix[i] == '(')
{
push(infix[i]);
b++;
}
else if (infix[i] == ')')
{
b++;
while (stack[top] != '(')
{
y = pop();
postfix[j] = y;
j++;
}
y = pop();
}
else
{
prec1 = check(infix[i]);
prec2 = 4;
while (stack[top] != '(' && prec2 >= prec1)
{
prec2 = check(stack[top]);
if (prec2 >= prec1)
{
postfix[j] = pop();
j++;
}
}
push(infix[i]);
}
}

n = n - b + 1;

printf("\n%s", "THE EQUIVALENT POSTFIX EXPRESSION IS : ");

for (i = 0; i < n; i++)
printf("%c ", postfix[i]);
printf("\n\n");

/* evaluation of the postfix expression */
for (i = 0; i < n; i++)
{
tempa[0] = postfix[i];
j = atoi(tempa);
postfix1[i] = j;
}

answer = 0;
top1 = -1;

for (i = 0; i < n; i++)
{
if (postfix[i] >= '0' && postfix[i] <= '9')
push1(postfix1[i]);
else
{
bf = pop1();
af = pop1();

switch(postfix[i])
{
case '+':
answer = af + bf;
break;
case '-':
answer = af - bf;
break;
case '*':
answer = af * bf;
break;
case '/':
answer = af / bf;
break;
case '^':
answer = pow(af, bf);
break;
}

push1(answer);
}
}

printf("%s %f", "THE VALUE OF THE EXPRESSION ENTERED IS :", answer);
getch();
}

You use "conio.h" for the sole purpose of being able to clear the screen, which isn't necessary or even desirable for most commandline users. Further, using this header file almost instantly makes your program limited to Windows.

Get rid of it and be better for doing so.
You create global variables. Global variables make your code brittle, and hard to maintain and modify. Instead of using globals, pass things through function arguments.
You didn't specify explicitly that this is C and not C++. Others here will likely get confused as this forum primarily serves C++ programmers. You're not unwelcome, but the difference needs to be made clear.
Your main doesn't return int. "main" should always return int, so that it can tell the OS whether or not it succeeded, or if it failed, in what way. Smilarly, there's no need to use "void" in the argument list. You don't do this with the functions you create, and they still work.

The key, I think, is to dump the antiquated Turbo C. Get GCC and come into the modern, portable world.

At least it doesn't have you writing K&R C...
You're including too much logic in main. You should break this down into functions and procedures with meaningful names.

On that last point, let's create a set of functions which handle stack operations. The functions for handling char stack and float stacks are nearly identical.

I've also included the stdbool header file so I can deal with booleans in a standard manner. The "bool" type is part of C++, but not C by default.

code:

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

#define STACK_DEPTH 50

/* FUNCTIONS FOR CHARACTER STACK HANDLING */

/* Initialize the variables for a char stack */
void char_stack_init(char stack[], int * top)
{
*top = 0;
for (int i = 0; i < STACK_DEPTH; i++)
{
stack[i] = 0;
}
}

/* We need to know if the stack can accept more values
If it is, we can't push values onto it.
*/
bool char_stack_full(int top)
{
return top >= STACK_DEPTH - 1;
}

/* We alo need to know if it's empty
If it is, we can't pop values from it.
*/
bool char_stack_empty(int top)
{
return top < 0;
}

/* Push a character onto a stac, but only it the stack can accept
more. If it can, increment top. Otherwise return false.
*/
bool char_stack_push(char stack[], int * top, char newItem)
{
if (!char_stack_full(*top))
{
stack[*top++] = newItem;
return true;
}
else
{
return false;
}
}

/* Pop a value, if that's possible. If it is, decrement
top and return true. Otherwise return false.
*/
bool char_stack_pop(char stack[], int * top, char * output)
{
if (!char_stack_empty(*top))
{
*output = stack[*top--];
return true;
}
else
{
return false;
}
}

/* FUNCTIONS FOR FLOAT STACK HANDLING */

/* Initialize the variables for a char stack */
void float_stack_init(float stack[], int * top)
{
*top = 0;
for (int i = 0; i < STACK_DEPTH; i++)
{
stack[i] = 0;
}
}

/* We need to know if the stack can accept more values
If it is, we can't push values onto it.
*/
bool float_stack_full(int top)
{
return top >= STACK_DEPTH - 1;
}

/* We alo need to know if it's empty
If it is, we can't pop values from it.
*/
bool float_stack_empty(int top)
{
return top < 0;
}

/* Push a character onto a stack, but only it the stack can accept
more. If it can, increment top. Otherwise return false.
*/
bool float_stack_push(float stack[], int * top, float newItem)
{
if (!float_stack_full(*top))
{
stack[*top++] = newItem;
return true;
}
else
{
return false;
}
}

/* Pop a value, if that's possible. If it is, decrement
top and return true. Otherwise return false.
*/
bool float_stack_pop(char stack[], int * top, float * output)
{
if (!float_stack_empty(*top))
{
*output = stack[*top--];
return true;
}
else
{
return false;
}
}

int main()
{
char stack[STACK_DEPTH];
int top;
char value;

char_stack_init(stack, &top);
char_stack_push(stack, &top, 'A');
char_stack_pop(stack, &top, &value);

printf("%c", value);

return 0;
}

Now, let's turn our attention to your function to check the precendence level of an operator. First off, it's wonderful that you've broken this out into a function!

However, you're doing a bit too much work in the switch.

If two cases have the same result, we can rewrite the switch thusly:

code:

int check(char operator)
{
int prec = 0;

switch (operator)
{
case '+': case '-':
prec = 1;
break;
case '*': case '/':
prec = 2;
break;
case '^':
prec = 3;
break;
default :
prec = 0;
}

return(prec);
}

Further, assigning to the variable, then returning its value is redundant. We can return from inside the switch. This also means we can remove all of those breaks, as well as the variable declaration, the assignment, and the return at the end of the function.

code:

int check(char operator)
{
switch (operator)
{
case '+': case '-':
return 1;
case '*': case '/':
return 2;
case '^':
return 3;
default :
return 0;
}
}

One last thing, "check" isn't a very descriptive name. Try changing it to something like "evaluate_operator_precendence".

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members