Thread: Stack that evaluates postfix expressions

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    43

    Stack that evaluates postfix expressions

    hello..my goal here is to take the stack program that i already have and use it to evaluate postfix expressions from a file. I need help figuring out how to modify the stack to work with integers and evaluate the expressions. Any suggestions?
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <ctype.h>
    #include <string.h>
    
    #define TRUE 1
    #define FALSE 0
    struct info_node
    {
    	int weight ;
    	struct info_node* next ;
    
    } ;
    
    struct nstack
    {
    	struct info_node* top ;
    } ;
    
    
    void create_stack(struct nstack*) ;
    int empty_stack(struct nstack*) ;
    void push_stack(struct nstack* , struct info_node*) ;
    
    struct info_node* pop_stack( struct nstack* ) ;
    
    
    
    int main()
    {
    FILE* infile ;
    int a = 0 ;
    int num = 0 ;
    struct nstack even_Stack ;
    struct nstack odd_Stack ;
    struct info_node* pnew_node = NULL ;
    struct info_node* ppop_node = NULL ;
    
    
    				create_stack(&even_Stack) ;
    				create_stack(&odd_Stack) ;
    
    				infile = fopen("express.txt", "r") ;
    
    				while (!feof( infile ) )
    				{
    					a++ ;
    					fscanf(infile, "%d" , &num) ;
    
    					pnew_node = (struct info_node* ) malloc(sizeof(info_node) ) ;
    					
    					pnew_node->weight = num ;
    					pnew_node->next = NULL ;
    
    					if( (num % 2) == 0 )
    						push_stack(&even_Stack, pnew_node) ;
    					else
    						push_stack(&odd_Stack, pnew_node) ;
    
    
    				}
    
    	while( !empty_stack(&even_Stack) )
    	{
    		ppop_node = pop_stack(&even_Stack) ;
    		num = ppop_node-> weight ;
    
    		printf("%d ", num ) ;
    
    		a++;
    		if( (a % 20) == 0 )
    			printf("\n") ;
    		
    	}
    	printf("\n\n") ;
    	a = 0 ;
    		while( !empty_stack(&odd_Stack) )
    	{
    		ppop_node = pop_stack(&odd_Stack) ;
    		num = ppop_node-> weight ;
    
    		printf("%d ", num ) ;
    
    		a++;
    		if( (a % 20) == 0 )
    			printf("\n") ;
    		
    	}
    
    
    		fclose(infile) ;
    	return (0) ;
    
    
    } //end of func main
    
    void create_stack(struct nstack* pnstack)
    {
    	pnstack->top = NULL ;
    	return ;
    
    } //end of func create_stack
    
    int empty_stack(struct nstack* pnstack)
    {
    	if (pnstack->top == NULL)
    		return (TRUE) ;
    	else
    		return (FALSE) ;
    
    } //end of func empty_stack
    
    void push_stack(struct nstack* pnstack, struct info_node* pnnode)
    {
    	if(empty_stack(pnstack))
    	{
    		pnstack->top = pnnode ;
    		pnnode->next = NULL ;
    	}
    	else
    	{
    		pnnode->next = pnstack->top ;
    		pnstack->top = pnnode ;
    	}
    	return ;
    
    } //end of func push_stack
    
    struct info_node* pop_stack( struct nstack* pnstack )
    {
    	struct info_node* prnode = NULL ;
    
    	if(empty_stack(pnstack) )
    		printf("ERROR: STACK IS EMPTY!!! \n") ;
    	else
    	{
    		prnode = pnstack->top ;
    		pnstack->top = pnstack->top->next ;
    		prnode->next = NULL ;
    	}
    	
    	return( prnode ) ;
    
    } // end of func pop_stack
    
    int calc(int operand1, int oper, int operand2)
    {
    	//Local Declaration
    	int result = 0 ;
    
    	//Statements
    
    	switch(oper)
    	{
    	case '+' : result = operand1 + operand2;
    	break ;
    	case '-' : result = operand1 - operand2;
    	break ;
    	case '*' : result = operand1 * operand2;
    	break ;
    	case '/' : result = operand1 / operand2;
    	break;
    	} //end of switch(oper)
    	return (result) ;
    } //end of function calc()


    Also these are the expressions i am supposed to read in from a file(express.txt):
    1 2 3 * 4 / +
    1 2 3 4 / * +
    1 2 + 3 * 4 /
    1 2 + 4 3 / *
    1 2 3 * + 4 /
    4 3 / 1 2 + *
    6 7 8 / 9 * -
    6 7 8 9 * / -
    6 7 - 8 / 9 *
    6 7 - 9 8 * /
    6 7 8 / - 9 *
    8 9 * 6 7 - /

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    i havent looked at the code, because it doesnt matter. it seems your having a problem with the logic (nothing related to C code) of how to accomplish this.

    for the first line, we have: "1 2 3 * 4 / +". now you know what a stack is: a FILO data structure. and files are read sequentially, so you only know what has been read (not the rest of the line). also, you will be reading the file one character at a time. running through it:
    - read '1' it is a number so memorize or store it somewhere (ie a stack?)
    - read '2', it is a number so save
    - read '3', number => save
    - read '*', not a number so do the calculation '2 * 3' = 6 and save
    - read '4', number => save
    - read '/', not a number so do the calculation '6 / 4' = 3/2 and save (note if you are using only integers, then your result will be approximated and not exact!)
    - read '+', not a number so do the calculation '1 + 3/2' = 5/2 and save
    - read newline, we are done

    hopefully you can understand that and implement what you need to do

    edit: note: the "=>" is a symbol used in logic and means "implies", it has nothing to do with '=' or '>' mathematical symbols
    Last edited by nadroj; 10-01-2008 at 05:17 PM.

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    As nadroj says, you've already got the stack, and the stack already contains ints, so that's all good then.

    You will need to be careful about input, since you don't know ahead of time whether you need to read a number or an operator; when I've done this in the past I read a whole line with fgets and then split it up with strtok, but there are certainly other methods.

  4. #4
    Registered User
    Join Date
    Mar 2008
    Posts
    43
    i understand the logic and how postfix expressions in the stack work..its translating that to code is what im having trouble with

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by killmequick View Post
    i understand the logic and how postfix expressions in the stack work..its translating that to code is what im having trouble with
    I don't see how that's possible; if the logic is "pop the stack twice" and the code says "pop_stack" how hard can that actually be?

  6. #6
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    i thought i was actually giving too much of an answer. what i wrote is basically the english version (pseudocode) of the answer

  7. #7
    Registered User
    Join Date
    Mar 2008
    Posts
    43
    well i thank you i understand what is going on..but one more question. how can i modify my stack to work with integers

  8. #8
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    in your stack you have a struct to represent a node in the stack. in this you need a pointer to the next node, as well as a variable that holds the data, which you have. what datatype does your stack hold 'data' for?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. stack and pointer problem
    By ramaadhitia in forum C Programming
    Replies: 2
    Last Post: 09-11-2006, 11:41 PM
  2. Replies: 4
    Last Post: 03-12-2006, 02:17 PM
  3. Question about a stack using array of pointers
    By Ricochet in forum C++ Programming
    Replies: 6
    Last Post: 11-17-2003, 10:12 PM
  4. error trying to compile stack program
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2003, 06:27 PM
  5. Stack Program Here
    By Troll_King in forum C Programming
    Replies: 7
    Last Post: 10-15-2001, 05:36 PM