So basically I need to find a way to evaluate an infix that's been converted into a postfix. The code below takes an entered infix and converts it into a postfix but I don't know how to take that postfix and evaluate it. Every single tutorial I've seen evaluates a postfix entered directly instead of a infix, so I have no clue what to do. So i decided to ask for help in doing this.

Though to be honest, I'm more interested in reading material then direct code so I can understand it. But if you explain the code, that'd work too.

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <string.h>
#include <ctype.h>
#pragma warning(disable: 4996)
#define MAX 50
#define EMPTY -1


//Construct the Stack that is to be manipulated by the code
struct stack
{
    
	int data[MAX];// Allow for "max" chracter input
    int top;// To be used when "moving" a part of the stack

};//End of stack contruction
 
// Determine if a stack is empty when manipulating the stack
void emptystack(struct stack* s)
{
    s->top=EMPTY;
}//End of Empty Determin-er


int isempty(struct stack *s)
{
    return (s->top == EMPTY) ? 1 : 0;
}
 

void push(struct stack* s,int item)
{
    if(s->top == (MAX-1))
    {
        printf("\nSTACK FULL");
    }
    else
    {
        ++s->top;
        s->data[s->top]=item;
    }
}
 
int pop(struct stack* s)
{
    int ret=EMPTY;
    if(s->top == EMPTY)
        printf("\nSTACK EMPTY");
    else
    {
        ret= s->data[s->top];
        --s->top;
    }
    return ret;
}

void display(struct stack s)
{
    while(s.top != EMPTY)
    {
        printf("\n%d",s.data[s.top]);
        s.top--;
    }
}

//Determines what operators can be used in accordence to the code
char isoperator(char e)
{
    if(e == '+' || e == '-' || e == '*' || e == '/' || e == '%')
        return 1;
    else
        return 0;
}//END of operator determin-er 
 
//Determines the priority of the operators in relation to each other 
char priority(char e)
{
    int pri = 0;
 
    if(e == '*' || e == '/' || e =='%')
        pri = 2;
    else
    {
        if(e == '+' || e == '-')
            pri = 1;
    }
    return pri;
}//End of priority Determin-er 
 

//Changes Infix notation into prefix notation
void infix2postfix(char* infix, char * postfix, int insertspace)
{
    char *i,*p; //Varibles for the infix and postfix of the stack
    struct stack X; // Variable for the precontructed stack
    char n1;
    emptystack(&X);
    i = &infix[0]; //Determines the use of the "i variable"
    p = &postfix[0]; //Determines the use of the "i variable"

	//While loop for when a person uses a space when entering the stack
    while(*i)
    {
        while(*i == ' ' || *i == '\t')
        {
            i++;
        }
 
	       if( isdigit(*i) || isalpha(*i) )
        {
            while( isdigit(*i) || isalpha(*i))
            {
                *p = *i;
                p++;
                i++;
            }
            /*SPACE CODE*/
            if(insertspace)
            {
                *p = ' ';
                p++;
            }
            /*END SPACE CODE*/
        }
 
        if( *i == '(' )
        {
            push(&X,*i);
            i++;
        }
 
        if( *i == ')')
        {
            n1 = pop(&X);
            while( n1 != '(' )
            {
                *p = n1;
                p++;
                /*SPACE CODE*/
                if(insertspace)
				{
                    *p = ' ';
                    p++;
                }
                /*END SPACE CODE*/
                n1 = pop(&X);
            }
            i++;
        }
 
        if( isoperator(*i) )
        {
            if(isempty(&X))
                push(&X,*i);
            else
            {
                n1 = pop(&X);
                while(priority(n1) >= priority(*i))
                {
                    *p = n1;
                    p++;
                    /*SPACE CODE*/
                    if(insertspace)
                    {
                        *p = ' ';
                        p++;
                    }
                    /*END SPACE CODE*/
                    n1 = pop(&X);
                }
                push(&X,n1);
                push(&X,*i);
            }
            i++;
        }
    }

    while(!isempty(&X))
    {
        n1 = pop(&X);
        *p = n1;
        p++;
        /*SPACE CODE*/
        if(insertspace)
        {
            *p = ' ';
            p++;
        }
        /*END SPACE CODE*/
    }
	*p = '\0';
}

int main()
{
    char in[50] = { 0 },post[50] = { 0 };
 
    strcpy(&post[0],"");
    printf("Enter Infix Expression: ");   

	fgets(in, sizeof(in), stdin);
		in[strlen(in) - 1] = '\0';
	infix2postfix(&in[0],&post[0],1);
    printf("Postfix Expression is: %s\n",&post[0]);//Prints Infix expression
	

	std::getchar();
    
	return 0;

	
}

Edited 5 Years Ago by ThatGuywithCode: n/a

The code below takes an entered infix and converts it into a postfix but I don't know how to take that postfix and evaluate it. Every single tutorial I've seen evaluates a postfix entered directly instead of a infix, so I have no clue what to do.

I don't understand the problem. Postfix is Postfix, isn't it? What's the difference between entering Postfix directly, or having Infix converted to Postfix and using that?

Think about it this way. If you're making spaghetti and you need tomato puree, does it matter whether you open a can of tomato puree or you open a can of whole tomatoes and puree them in a blender?

I don't understand the problem. Postfix is Postfix, isn't it? What's the difference between entering Postfix directly, or having Infix converted to Postfix and using that?

Think about it this way. If you're making spaghetti and you need tomato puree, does it matter whether you open a can of tomato puree or you open a can of whole tomatoes and puree them in a blender?

I somewhat get you. Use the results of my conversion and make it evaluate. The problem is the tutorials I found don't really explain the code in terms of evaluation. As in I'm not sure what specific snippets do what to actually evaluate it.

I might be able to get this is someone can give an example of an evaluation program and tell me what snippets do what (like with comments.... which every tutorial I've found seems to lack...)

This is homework, isn't it...

If so, aren't you supposed to learn how to actually do postfix notation, and then be able to program it? First thing is to understand what postfix is, and how it works. Reading someone's code is not the way to learn it.

Do you need to find some good explanations on how to understand postfix and it's evaluation?
Start with http://en.wikipedia.org/wiki/Reverse_Polish_notation

Edited 5 Years Ago by WaltP: n/a

This is homework, isn't it...

If so, aren't you supposed to learn how to actually do postfix notation, and then be able to program it? First thing is to understand what postfix is, and how it works. Reading someone's code is not the way to learn it.

Do you need to find some good explanations on how to understand postfix and it's evaluation?
Start with http://en.wikipedia.org/wiki/Reverse_Polish_notation

Not 100% sure what your saying. The code I put in the original post IS an infix to postfix converter. I know how to convert infix to postfix and prefix. What I don't know and am asking for is how to evaluate the postfix code like it was in infix notation in C++.

As in I enter an infix notation equation, it's converted to postfix, and that post fix is evaluated. What I'm hoping for is an explanation on how, in C++, postfix is evaluated. I know the mathamatic way it's done I just can't express it in code.

Not 100% sure what your saying. The code I put in the original post IS an infix to postfix converter. I know how to convert infix to postfix and prefix. What I don't know and am asking for is how to evaluate the postfix code like it was in infix notation in C++.

Confused. You can't "evaluate the postfix code like it was in infix notation". It's Postfix. Try giving an example. Words don't always do the job, especially when you aren't even sure of what you're asking.

As in I enter an infix notation equation, it's converted to postfix, and that post fix is evaluated. What I'm hoping for is an explanation on how, in C++, postfix is evaluated. I know the mathamatic way it's done I just can't express it in code.

If you know the mathmatical way, you need to
1) write down the decisions and steps themselves as a guide. This becomes your algorithm.
2) Now break each step/decision into smaller steps.
3) When the steps are broken down small enough, use the steps to evaluate a few equations. Make sure the steps are in the proper order to evaluate your equation.
4) This is when you can translate the steps into code. Just follow the roadmap you've created.

This is how programming is done:

Design (1), no computer involved.
Plan the process (2)
Verify the process (3)
Code (4), where the computer finally comes in.

Confused. You can't "evaluate the postfix code like it was in infix notation". It's Postfix. Try giving an example. Words don't always do the job, especially when you aren't even sure of what you're asking.


If you know the mathmatical way, you need to
1) write down the decisions and steps themselves as a guide. This becomes your algorithm.
2) Now break each step/decision into smaller steps.
3) When the steps are broken down small enough, use the steps to evaluate a few equations. Make sure the steps are in the proper order to evaluate your equation.
4) This is when you can translate the steps into code. Just follow the roadmap you've created.

This is how programming is done:

Design (1), no computer involved.
Plan the process (2)
Verify the process (3)
Code (4), where the computer finally comes in.

Ah I see.

Though what i meant was get the same results of the infix notation as in
1+2-3 = 0 <- I can do this
1 2 + 3- = 0 <- I don't know how a computer evaluates this

I think it(the computer) reads the equation from left to right, find the numbers and then evaluates them based on the following operator and continues do do that till it reaches the end.

Problem is I'm not sure how to pull that off code wise. Having the infix converted into postfix wasn't that hard because I can identify the individual operators as characters.

According to my research I can perform it using a modified version of "pop" that reads the converted infix (the postfix) as a string. However I'm not sure how to go about that, because what I want to do is have it all in the same .cpp file, meaning pop is doing more then one "type" of pop. It's here where I'm stuck because I'm not sure how to go about that... or if I CAN do that.

Edited 5 Years Ago by ThatGuywithCode: n/a

Okay I figured out how to evaluate it(really simple atually), but no mater what I enter for the infix it converts to postfix (it's suppose to do that) but it always produces an answer of "-1" for the evaluation.

"New" code below

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <string.h>
#include <ctype.h>
#pragma warning(disable: 4996)
#define MAX 50
#define EMPTY -1


//Construct the Stack that is to be manipulated by the code
struct stack
{

int data[MAX];// Allow for "max" chracter input
int top;// To be used when "moving" a part of the stack

};//End of stack contruction

// Determine if a stack is empty when manipulating the stack
void emptystack(struct stack* s)
{
s->top=EMPTY;
}//End of Empty Determin-er


int isempty(struct stack *s)
{
return (s->top == EMPTY) ? 1 : 0;
}


void push(struct stack* s,int item)
{
if(s->top == (MAX-1))
{
printf("\nSTACK FULL");
}
else
{
++s->top;
s->data[s->top]=item;
}
}

char pop(struct stack* s)
{
char ret=(char)EMPTY;
if(!isempty(s))
{
ret= s->data[s->top];
--s->top;
}
return ret;
}


void display(struct stack s)
{
while(s.top != EMPTY)
{
printf("\n%d",s.data[s.top]);
s.top--;
}
}

//Determines what operators can be used in accordence to the code
char isoperator(char e)
{
if(e == '+' || e == '-' || e == '*' || e == '/' || e == '%')
return 1;
else
return 0;
}//END of operator determin-er

//Determines the priority of the operators in relation to each other
char priority(char e)
{
int pri = 0;

if(e == '*' || e == '/' || e =='%')
pri = 2;
else
{
if(e == '+' || e == '-')
pri = 1;
}
return pri;
}//End of priority Determin-er


//Changes Infix notation into prefix notation
void infix2postfix(char* infix, char * postfix, int insertspace)
{
char *i,*p; //Varibles for the infix and postfix of the stack
struct stack X; // Variable for the precontructed stack
char n1;
emptystack(&X);
i = &infix[0]; //Determines the use of the "i variable"
p = &postfix[0]; //Determines the use of the "i variable"

//While loop for when a person uses a space when entering the stack
while(*i)
{
while(*i == ' ' || *i == '\t')
{
i++;
}

if( isdigit(*i) || isalpha(*i) )
{
while( isdigit(*i) || isalpha(*i))
{
*p = *i;
p++;
i++;
}
/*SPACE CODE*/
if(insertspace)
{
*p = ' ';
p++;
}
/*END SPACE CODE*/
}

if( *i == '(' )
{
push(&X,*i);
i++;
}

if( *i == ')')
{
n1 = pop(&X);
while( n1 != '(' )
{
*p = n1;
p++;
/*SPACE CODE*/
if(insertspace)
{
*p = ' ';
p++;
}
/*END SPACE CODE*/
n1 = pop(&X);
}
i++;
}

if( isoperator(*i) )
{
if(isempty(&X))
push(&X,*i);
else
{
n1 = pop(&X);
while(priority(n1) >= priority(*i))
{
*p = n1;
p++;
/*SPACE CODE*/
if(insertspace)
{
*p = ' ';
p++;
}
/*END SPACE CODE*/
n1 = pop(&X);
}
push(&X,n1);
push(&X,*i);
}
i++;
}
}

while(!isempty(&X))
{
n1 = pop(&X);
*p = n1;
p++;
/*SPACE CODE*/
if(insertspace)
{
*p = ' ';
p++;
}
/*END SPACE CODE*/
}
*p = '\0';
}

//Evaluates the stack

int evaluate(char *postfix)
{
char *p;
struct stack X;
int op1,op2,result;

emptystack(&X);
p = &postfix[0];

while(*p != '\0')
{
/* removes tabs and spaces */
while(*p == ' ' || *p == '\t')
{
p++;
}
/* if is digit */
if(isdigit(*p))
{
push(&X,*p - 48);
}
else
{
/* it is an operator */
op1 = pop(&X);
op2 = pop(&X);

switch(*p)
{
case '+':
result = op2 + op1;
break;

case '-':
result = op2 - op1;
break;

case '/':
result = op2 / op1;
break;

case '*':
result = op2 * op1;
break;

case '%':
result = op2 % op1;
break;

default:
printf("\nInvalid Operator");
return 0;
}
push(&X,result);
}
p++;
}
result = pop(&X);
return result;
}


int main()
{
char in[50] = { 0 },post[50] = { 0 };

strcpy(&post[0],"");
printf("Enter Infix Expression: ");

fgets(in, sizeof(in), stdin);
in[strlen(in) - 1] = '\0';
infix2postfix(&in[0],&post[0],1);
printf("Postfix Expression is: %s\n",&post[0]);//Prints Infix expression

fgets(post, sizeof(post), stdin);
post[strlen(post) - 1] = '\0';
printf("%s EQUALS %d\n",post,evaluate(&post[0]));

std::getchar();

return 0;


}

Edited 5 Years Ago by ThatGuywithCode: n/a

Ah I see.

Though what i meant was get the same results of the infix notation as in
1+2-3 = 0 <- I can do this
1 2 + 3- = 0 <- I don't know how a computer evaluates this

A computer doesn't evaluate it. A program, written by you, does. You take your knowledge and convert it into a program (like the previous post).

As for your code, without proper formatting I'm not even going to try to follow it. It's hard enough understanding someone else's code without adding the difficulty of no indentation at all.

Fixed everything. If anyone needs this the "fixed" code is posted below. Thanks by the way, what you said allowed me to take a step back and properly analyze it.

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <string.h>
#include <ctype.h>
#pragma warning(disable: 4996)
#define MAX 50
#define EMPTY -1


//Construct the Stack that is to be manipulated by the code
struct stack
{
    
	int data[MAX];// Allow for "max" chracter input
    int top;// To be used when "moving" a part of the stack

};//End of stack contruction
 
// Determine if a stack is empty when manipulating the stack
void emptystack(struct stack* s)
{
    s->top=EMPTY;
}//End of Empty Determin-er


int isempty(struct stack *s)
{
    return (s->top == EMPTY) ? 1 : 0;
}
 

void push(struct stack* s,int item)
{
    if(s->top == (MAX-1))
    {
        printf("\nSTACK FULL");
    }
    else
    {
        ++s->top;
        s->data[s->top]=item;
    }
}
 
char pop(struct stack* s)
{
    char ret=(char)EMPTY;
    if(!isempty(s))
    {
        ret= s->data[s->top];
        --s->top;
    }
    return ret;
}
 

void display(struct stack s)
{
    while(s.top != EMPTY)
    {
        printf("\n%d",s.data[s.top]);
        s.top--;
    }
}

//Determines what operators can be used in accordence to the code
char isoperator(char e)
{
    if(e == '+' || e == '-' || e == '*' || e == '/' || e == '%')
        return 1;
    else
        return 0;
}//END of operator determin-er 
 
//Determines the priority of the operators in relation to each other 
char priority(char e)
{
    int pri = 0;
 
    if(e == '*' || e == '/' || e =='%')
        pri = 2;
    else
    {
        if(e == '+' || e == '-')
            pri = 1;
    }
    return pri;
}//End of priority Determin-er 
 

//Changes Infix notation into prefix notation
void infix2postfix(char* infix, char * postfix, int insertspace)
{
    char *i,*p; //Varibles for the infix and postfix of the stack
    struct stack X; // Variable for the precontructed stack
    char n1;
    emptystack(&X);
    i = &infix[0]; //Determines the use of the "i variable"
    p = &postfix[0]; //Determines the use of the "i variable"

	//While loop for when a person uses a space when entering the stack
    while(*i)
    {
        while(*i == ' ' || *i == '\t')
        {
            i++;
        }
 
	       if( isdigit(*i) || isalpha(*i) )
        {
            while( isdigit(*i) || isalpha(*i))
            {
                *p = *i;
                p++;
                i++;
            }
            /*SPACE CODE*/
            if(insertspace)
            {
                *p = ' ';
                p++;
            }
            /*END SPACE CODE*/
        }
 
        if( *i == '(' )
        {
            push(&X,*i);
            i++;
        }
 
        if( *i == ')')
        {
            n1 = pop(&X);
            while( n1 != '(' )
            {
                *p = n1;
                p++;
                /*SPACE CODE*/
                if(insertspace)
				{
                    *p = ' ';
                    p++;
                }
                /*END SPACE CODE*/
                n1 = pop(&X);
            }
            i++;
        }
 
        if( isoperator(*i) )
        {
            if(isempty(&X))
                push(&X,*i);
            else
            {
                n1 = pop(&X);
                while(priority(n1) >= priority(*i))
                {
                    *p = n1;
                    p++;
                    /*SPACE CODE*/
                    if(insertspace)
                    {
                        *p = ' ';
                        p++;
                    }
                    /*END SPACE CODE*/
                    n1 = pop(&X);
                }
                push(&X,n1);
                push(&X,*i);
            }
            i++;
        }
    }

    while(!isempty(&X))
    {
        n1 = pop(&X);
        *p = n1;
        p++;
        /*SPACE CODE*/
        if(insertspace)
        {
            *p = ' ';
            p++;
        }
        /*END SPACE CODE*/
    }
	*p = '\0';
}

//Evaluates the stack
 
int evaluate(char *postfix)
{
    char *p;
    struct stack X;
    int op1,op2,result;
 
    emptystack(&X);
    p = &postfix[0];
 
    while(*p != '\0')
    {
       /* removes tabs and spaces */
        while(*p == ' ' || *p == '\t')
        {
            p++;
        }
      /* if is digit */
        if(isdigit(*p))
        {
            push(&X,*p - 48);
        }
        else
        {
           /* it is an operator */
            op1 = pop(&X);
            op2 = pop(&X);
 
				switch(*p)
            {
                case '+':
                    result = op2 + op1;
                    break;
 
                case '-':
                    result = op2 - op1;
                    break;
 
                case '/':
                    result = op2 / op1;
                    break;
 
                case '*':
                    result = op2 * op1;
                    break;
 
                case '%':
                    result = op2 % op1;
                    break;
 
                default:
                    return result;
            }
            push(&X,result);
        }
        p++;
    }
    result = pop(&X);
    return result;
}


int main()
{
    char in[50] = { 0 },post[50] = { 0 };
 
    strcpy(&post[0],"");
    printf("Enter Infix Expression: ");   

	fgets(in, sizeof(in), stdin);
		in[strlen(in) - 1] = '\0';
	infix2postfix(&in[0],&post[0],1);
    printf("Postfix Expression is: %s\n",&post[0]);
	
	fgets(in, sizeof(in), stdin);
        post[strlen(post) - 1] = '\0';
    printf(" %s EQUALS %d\n",post,evaluate(&post[0]));	

	std::getchar();
    
	return 0;

	
}

Excellent!

Nicely formatted (up until main() )
Commented (could use a few more but much better than most code here)
No glaring use if undefined behavior
And no conio.h!! Yippee!!!

This question has already been answered. Start a new discussion instead.