12 Replies - 3173 Views - Last Post: 03 October 2012 - 09:45 PM Rate Topic: -----

#1 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Postfix expression evaluation from a file trouble using stacks

Posted 02 October 2012 - 06:24 PM

Hello so I am running into a few issues regarding a programming project in which I am to set up a program that calculates several postfix expressions from a file input. First I can't seem to get my program to push the numbers from the file into my numbers stack correctly, which then throws off all the calculations I need to make. Another issue is that when the data copies to my string, I cant seem to get numbers that are larger than one digit to stay together, so if I do a cout<<expression[i] and step through the string, a number like 100 looks like 1, 0, 0 so I am not entirely sure how to copy that correctly to my string. Below is my program and associated files, along with what the desired output should look like. (I attached the txt file below that holds the expressions I need to calculate). Also I should say that I am restricted to copying the data from this txt file to either a string or a char array.

Program I am working on:
// Beginning of program
#include <iostream>  //provides cout, cinm peek, ignore
#include <cstdlib> //Provides EXIT_SUCCESS
#include <fstream> //For Files
#include <cctype> //Provides isdigit
#include <cstring>
#include "stack2.h"//For stack template class

using namespace std;
using namespace main_savitch_7B;

int main()
{    
    stack <double> numbers;//A stack of numbers
    int stackSize = 0;
    double number, operand1, operand2;
    char token;
    string expression;
       
    //File initialization
    ifstream ins;
    //Connect to file
    ins.open("HomeworkSixInput.txt"); 
    
    //Opening file error failsafe
    if (ins.fail())
    {
        cout<< "Instream file failed to open.\n";
        exit(1);
    }
           
    cout<< "*************************************\n";
    cout<< "CSC-161 Homework Six Solution\n";
    cout<< "\nInput file expressions and values:\n\n";
    
        while (!ins.eof())
        {                                                                                                      
             getline(ins, expression, '\n');
             
             int i = 0;      
             token = expression[i];           
             while (i < expression.size())
             {                                                  
                 //Pushing numbers onto stack
                 if (isdigit(token))
                 {                     
                      numbers.push(token);
                      stackSize++;
                 }
                 
                 else 
                 {                      
                      operand2 = numbers.top();
                      numbers.pop();
                      operand1 = numbers.top();
                      numbers.pop();
                      
                      switch (token)
                      {
                           case '+': numbers.push(operand1 + operand2);
                                     break;
                           case '-': numbers.push(operand1 - operand2);
                                     break;
                           case '*': numbers.push(operand1 * operand2);
                                     break;
                           case '/': numbers.push(operand1 / operand2);
                                     break;
                      }
                  } 
                  i++; 
          }
               if (stackSize != 1)
               {
                    cout<< expression << " is an invalid expression\n";             
               }
               
               else
               {
                    cout<< expression << " is equal to: ";
                    cout<<numbers.top()<<endl;
               }
          }
                                                                                                                                                                                
    //Program pause statement for inspection
    cout << "\nProgram is paused" << endl << endl; 
    system("Pause");     
    
    ins.close();//Close file input
    
    //End of program   
    return 0;
}


Stack header I am working with:
#ifndef MAIN_SAVITCH_STACK2_H
#define MAIN_SAVITCH_STACK2_H
#include <cstdlib>   // Provides NULL and size_t
#include "node2.h"   // Node template class from Figure 6.5 on page 308

namespace main_savitch_7B
{
    template <class Item>
    class stack
    {
    public:
        // TYPEDEFS 
        typedef std::size_t size_type;
        typedef Item value_type;
        // CONSTRUCTORS and DESTRUCTOR
        stack( ) { top_ptr = NULL; }
        stack(const stack& source);
        ~stack( ) { list_clear(top_ptr); }
        // MODIFICATION MEMBER FUNCTIONS
        void push(const Item& entry);
        void pop( );
        void operator =(const stack& source);
        // CONSTANT MEMBER FUNCTIONS
        size_type size( ) const
	    { return main_savitch_6B::list_length(top_ptr); }
        bool empty( ) const { return (top_ptr == NULL); }
        Item top( ) const;
    private:
        main_savitch_6B::node<Item> *top_ptr;  // Points to top of stack
    };
}


Stack template:
#include "stack2.template" // Include the implementation 
#endif

// FILE: stack2.template
// TEMPLATE CLASS IMPLEMENTED: stack<Item> (see stack2.h for documentation)
// This file is included in the header file, and not compiled separately.
// INVARIANT for the stack class:
//   1. The items in the stack are stored in a linked list, with the top of the
//      stack stored at the head node, down to the bottom of the stack at the
//      final node.
//   2. The member variable top_ptr is the head pointer of the linked list.

#include <cassert>  // Provides assert
#include "node2.h"  // Node template class

namespace main_savitch_7B
{
    template <class Item>
    stack<Item>::stack(const stack<Item>& source) 
    // Library facilities used: node2.h
    {
        main_savitch_6B::node<Item> *tail_ptr; // Needed for argument of list_copy

        list_copy(source.top_ptr, top_ptr, tail_ptr);
    }

    template <class Item>
    void stack<Item>::push(const Item& entry) 
    // Library facilities used: node2.h
    {
        list_head_insert(top_ptr, entry);
    }

    template <class Item>
    void stack<Item>::pop( )
    // Library facilities used: cassert, node2.h
    {
        assert(!empty( ));
        list_head_remove(top_ptr);
    }
    
    template <class Item>
    void stack<Item>::operator =(const stack<Item>& source) 
    // Library facilities used: node2.h
    {
        main_savitch_6B::node<Item> *tail_ptr; // Needed for argument of list_copy

        if (this == &source) // Handle self-assignment
            return;

        list_clear(top_ptr);
        list_copy(source.top_ptr, top_ptr, tail_ptr);
    }

    template <class Item>
    Item stack<Item>::top( ) const 
    // Library facilities used: cassert
    {
        assert(!empty( ));
        return top_ptr->data( );
    }
}



Node header for the stack template:
#ifndef MAIN_SAVITCH_NODE2_H  
#define MAIN_SAVITCH_NODE2_H
#include <cstdlib>   // Provides NULL and size_t
#include <iterator>  // Provides iterator and forward_iterator_tag

namespace main_savitch_6B
{
    template <class Item>
    class node
    {
    public:
        // TYPEDEF
        typedef Item value_type;
        // CONSTRUCTOR
        node(const Item& init_data=Item( ), node* init_link=NULL)
            { data_field = init_data; link_field = init_link; }
        // MODIFICATION MEMBER FUNCTIONS
        Item& data( ) { return data_field; }
        node* link( ) { return link_field; }
        void set_data(const Item& new_data) { data_field = new_data; }
        void set_link(node* new_link) { link_field = new_link; }
        // CONST MEMBER FUNCTIONS
        const Item& data( ) const { return data_field; }
        const node* link( ) const { return link_field; }
    private:
        Item data_field;
        node *link_field;
    };

    // FUNCTIONS to manipulate a linked list:
    template <class Item>
    void list_clear(node<Item>*& head_ptr);

    template <class Item>
    void list_copy
        (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr);

    template <class Item>
    void list_head_insert(node<Item>*& head_ptr, const Item& entry); 

    template <class Item>
    void list_head_remove(node<Item>*& head_ptr);

    template <class Item>
    void list_insert(node<Item>* previous_ptr, const Item& entry);
 
    template <class Item>
	std::size_t list_length(const node<Item>* head_ptr);

    template <class NodePtr, class SizeType>
    NodePtr list_locate(NodePtr head_ptr, SizeType position);

    template <class Item>
    void list_remove(node<Item>* previous_ptr);
   
    template <class NodePtr, class Item>
    NodePtr list_search(NodePtr head_ptr, const Item& target);

template <class Item>
    class node_iterator
    : public std::iterator<std::forward_iterator_tag, Item>
    {
    public:
    	node_iterator(node<Item>* initial = NULL)
	    { current = initial; }
	Item& operator *( ) const
	    { return current->data( ); }
	node_iterator& operator ++( ) // Prefix ++
	    { 
		current = current->link( );
		return *this;
	    }
	node_iterator operator ++(int) // Postfix ++
	    {
		node_iterator original(current);
		current = current->link( );
		return original;      	  
	    }
	bool operator ==(const node_iterator other) const
	    { return current == other.current; }
	bool operator !=(const node_iterator other) const
	    { return current != other.current; }
    private:
	node<Item>* current;
    };

    template <class Item>
    class const_node_iterator
    : public std::iterator<std::forward_iterator_tag, const Item>
    {
    public:
    	const_node_iterator(const node<Item>* initial = NULL)
	    { current = initial; }
	const Item& operator *( ) const
	    { return current->data( ); }
	const_node_iterator& operator ++( ) // Prefix ++
	    {
		current = current->link( );
		return *this;
	    }
	const_node_iterator operator ++(int) // Postfix ++
	    {
		const_node_iterator original(current);
		current = current->link( );
		return original;
	    }
	bool operator ==(const const_node_iterator other) const
	    { return current == other.current; }
	bool operator !=(const const_node_iterator other) const
	    { return current != other.current; }
    private:
	const node<Item>* current;
    };

}

#include "node2.template"
#endif



Node template
// FILE: node2.template
// IMPLEMENTS: The functions of the node template class and the
// linked list toolkit (see node2.h for documentation).
//
// NOTE:
//   Since node is a template class, this file is included in node2.h.
//   Therefore, we should not put any using directives in this file.
//
// INVARIANT for the node class:
//   The data of a node is stored in data_field, and the link in link_field.

#include <cassert>    // Provides assert
#include <cstdlib>    // Provides NULL and size_t

namespace main_savitch_6B
{
    template <class Item>
    void list_clear(node<Item>*& head_ptr)
    // Library facilities used: cstdlib
    {
	while (head_ptr != NULL)
	    list_head_remove(head_ptr);
    }

    template <class Item>
    void list_copy(
	const node<Item>* source_ptr,
	node<Item>*& head_ptr,
	node<Item>*& tail_ptr
	) 
    // Library facilities used: cstdlib
    {
	head_ptr = NULL;
	tail_ptr = NULL;

	// Handle the case of the empty list
	if (source_ptr == NULL)
	    return;	

	// Make the head node for the newly created list, and put data in it
	list_head_insert(head_ptr, source_ptr->data( ));
	tail_ptr = head_ptr; 
	
	// Copy rest of the nodes one at a time, adding at the tail of new list
	source_ptr = source_ptr->link( ); 
        while (source_ptr != NULL)
	{
	    list_insert(tail_ptr, source_ptr->data( ));
	    tail_ptr = tail_ptr->link( );
	    source_ptr = source_ptr->link( );
	}
    }
    
    template <class Item>
    void list_head_insert(node<Item>*& head_ptr, const Item& entry)
    {
	head_ptr = new node<Item>(entry, head_ptr);
    }

    template <class Item>
    void list_head_remove(node<Item>*& head_ptr)
    {
	node<Item> *remove_ptr;

	remove_ptr = head_ptr;
	head_ptr = head_ptr->link( );
	delete remove_ptr;
    }

    template <class Item>
    void list_insert(node<Item>* previous_ptr, const Item& entry) 
    {
	node<Item> *insert_ptr;
    
	insert_ptr = new node<Item>(entry, previous_ptr->link( ));
	previous_ptr->set_link(insert_ptr);
    }

    template <class Item>
    std::size_t list_length(const node<Item>* head_ptr)
    // Library facilities used: cstdlib
    {
	const node<Item> *cursor;
	std::size_t answer;
	
	answer = 0;
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
	    ++answer;
	
	return answer;
    }

    template <class NodePtr, class SizeType>
    NodePtr list_locate(NodePtr head_ptr, SizeType position) 
    // Library facilities used: cassert, cstdlib
    {
	NodePtr cursor;
	SizeType i;
    
	assert(0 < position);
	cursor = head_ptr;
	for (i = 1; (i < position) && (cursor != NULL); ++i)
	    cursor = cursor->link( );
	return cursor;
    }

    template <class Item>
    void list_remove(node<Item>* previous_ptr)
    {
	node<Item> *remove_ptr;

	remove_ptr = previous_ptr->link( );
	previous_ptr->set_link(remove_ptr->link( ));
	delete remove_ptr;
    }

    template <class NodePtr, class Item>
    NodePtr list_search(NodePtr head_ptr, const Item& target) 
    // Library facilities used: cstdlib
    {
	NodePtr cursor;
	
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
	    if (target == cursor->data( ))
		return cursor;
	return NULL;
    }
}



Desired output should look like this:
Input file expressions and values:

2 3 + 7 * is equal to 35
2 6 + 9 / is equal to 0.888889
14 2 + 160 / is equal to 0.1
99 2 + 50 / 24 - is equal to -21.98
100 4 / 3 * 20 + is equal to 95
10 2 3 + is an invalid expression
14 3 * 19 + 12 / 3 + 7 * is equal to 56.5833
23 7 + 10 * 14 + 19 - 22 * 16 / is equal to 405.625
19 2 + 14 / 15 3 / 2 + * is equal to 10.5
14 6 * 4 / 9 + is equal to 30


End of file
*************************************
Press any key to continue . . .

Attached File(s)



Is This A Good Question/Topic? 0
  • +

Replies To: Postfix expression evaluation from a file trouble using stacks

#2 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1344
  • View blog
  • Posts: 4,608
  • Joined: 19-February 09

Re: Postfix expression evaluation from a file trouble using stacks

Posted 02 October 2012 - 07:31 PM

Hi, your stack type is double and you are pushing char. Do you want to push both?

This post has been edited by #define: 02 October 2012 - 07:32 PM

Was This Post Helpful? 0
  • +
  • -

#3 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Re: Postfix expression evaluation from a file trouble using stacks

Posted 02 October 2012 - 08:08 PM

Shouldn't the isdigit() function check for that? From what I understand, it should be able to see that the current token is a number and therefore can be pushed into the stack of type double. I'm not intending to push both, but I am trying to get the numbers out of the file input and into the stack. Then I need to use the operators from the file to perform calculations.

Shouldn't the isdigit() function check for that? From what I understand, it should be able to see that the current token is a number and therefore can be pushed into the stack of type double. I'm not intending to push both, but I am trying to get the numbers out of the file input and into the stack. Then I need to use the operators from the file to perform calculations.
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3572
  • View blog
  • Posts: 11,107
  • Joined: 05-May 12

Re: Postfix expression evaluation from a file trouble using stacks

Posted 02 October 2012 - 08:13 PM

isdigit() just checks one character at a time. So if you have the number 23, and you perform isdigit('2'), the '3' will not be automatically picked up. Additionally, you are pushing unto the stack the character '2', not the value 2.
Was This Post Helpful? 0
  • +
  • -

#5 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Re: Postfix expression evaluation from a file trouble using stacks

Posted 02 October 2012 - 08:37 PM

Ah ok that sheds a lot of light on the results I'm getting. Hmm I'm trying to think of other solutions then, so I need to print the expression as well as the results of the expression. So to get the full number like 23, do I need to set up a double value to hold each input from the file? Like would ins >> value work? Or can I have the file input push values into the stack as it reads in data, then if it encounters an operator have it perform a calculation and push the result into the stack?
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3572
  • View blog
  • Posts: 11,107
  • Joined: 05-May 12

Re: Postfix expression evaluation from a file trouble using stacks

Posted 02 October 2012 - 08:50 PM

You only need the double value long enough to have parsed it from the input and to push it into the number stack.

There's a couple approaches to parsing:
- Once you find the first digit you can use atof() or a stringstream to convert the the digits into a double. You're still left with the problem of where to continue parsing once you've picked up the number, though.

- Once you find the first digit, keep collecting digits (and decimal points, and scientific notation characters if you support scientific notation) into a temporary string. Then use atof() or a stringstream to convert the temporary string into a double. You are then ready to continue parsing where you left off last time.

- Put entire line into a stringstream, and collect doubles and operators when you expect to see them. Works well for infix notation and if you are guaranteed to always have binary operators without regard to operator precedence. Otherwise, this approach usually tends to suck.

- Collect "token strings" as you go through the line input. Token strings are either a set of digits and decimal points (and maybe scientific notation characters); or an operator. If token is not an operator, parse the number. Basically the token acts the same as the temporary string in option #2 above.
Was This Post Helpful? 0
  • +
  • -

#7 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Re: Postfix expression evaluation from a file trouble using stacks

Posted 02 October 2012 - 09:20 PM

Is there not an easier way? the data doesn't necessarily have to be entered into the program via a string, but I do need a string to hold the initial expression then use the stack to calculate the expression into a final result. So the final input can be cout<< expression (the string)<< "is equal to: " << calculation (double type integer). I think that this is supposed to be a more basic operation than having to parse out all the data into several strings and then convert it.

Maybe an example of what this should look like in program will help? Say the file send the line:
19 2 +, the program should see 19, push it to the stack, then 2 and push it into the stack, then the + sign should cause 2 to pop out and be set to operand2, and 19 pops to operand1, the two get added together then the result gets pushed back into the stack.
Was This Post Helpful? 0
  • +
  • -

#8 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3572
  • View blog
  • Posts: 11,107
  • Joined: 05-May 12

Re: Postfix expression evaluation from a file trouble using stacks

Posted 02 October 2012 - 09:41 PM

With your current requirement of having to print out the original expression, and having multiple expressions in a single file, it becomes complicated. If you had one more operator '=' that is used to delimit the end of an expression, I can see a way to simplify things dramatically just by relying on the istream extraction operator, but alas, it is line breaks that acts as the end of expression marker.
Was This Post Helpful? 0
  • +
  • -

#9 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Re: Postfix expression evaluation from a file trouble using stacks

Posted 02 October 2012 - 09:56 PM

Hmm ok I'll keep playing with it and try out your suggestions. Thanks!
Was This Post Helpful? 0
  • +
  • -

#10 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1344
  • View blog
  • Posts: 4,608
  • Joined: 19-February 09

Re: Postfix expression evaluation from a file trouble using stacks

Posted 02 October 2012 - 10:50 PM

View PostBenedictRM, on 03 October 2012 - 07:20 AM, said:

Maybe an example of what this should look like in program will help? Say the file send the line:
19 2 +, the program should see 19, push it to the stack, then 2 and push it into the stack, then the + sign should cause 2 to pop out and be set to operand2, and 19 pops to operand1, the two get added together then the result gets pushed back into the stack.


Each token is separated by a space?

If each line is an expression use getline.

Use a stringstream to get each token as a string, ss >> token.

Test whether token string starts with a digit, use another stringstream to get double, ns >> number.

Otherwise string should contain operand, convert to char.

This post has been edited by #define: 02 October 2012 - 10:52 PM

Was This Post Helpful? 0
  • +
  • -

#11 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Re: Postfix expression evaluation from a file trouble using stacks

Posted 03 October 2012 - 02:21 PM

Ok so since I haven't used stringstreams before I am now trying to use a second string to hold the digits as they occur in the expression, and I am using substr to segment out the digits which the new string will be equal to, then I will convert that string in double and place those numbers into the stack. However in the code where I am trying to set the second string (called 'digit') I am having trouble getting the end value to set correctly -- the code I have posted below still captures some operations and sometimes partial expressions in the output. Since each digit is separated by a space I am trying to use that to mark the end of a potential digit (code below:

while (!ins.eof())
        {                                                                                                      
             getline(ins, expression, '\n');
                                        
             for (int i = 0; (i < expression.size()); ++i)
             { 
                  
                  if (isdigit(expression[i]))
                  {                      
                       begin = i;
                                       
                       while (!isspace(expression[i]))
                       {              
                            if(isdigit(expression[i]))
                            {
                                 i++;
                            }                           
                       }
                       end = i;
                                                           
                       digit = expression.substr(begin, end); 
                      
                       cout<< digit <<endl;                      
                  }
                                                                         
               }

}
Was This Post Helpful? 0
  • +
  • -

#12 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1344
  • View blog
  • Posts: 4,608
  • Joined: 19-February 09

Re: Postfix expression evaluation from a file trouble using stacks

Posted 03 October 2012 - 02:54 PM

The string digit will hold a number rather than a digit so would be better called number (or number_str).

The idea of incrementing the index within the loop seems a bit clunky, it is not needed.

During each iteration of the loop, if the character is a digit add it to the number string. If it is not a digit, test the number string has a size if so push on the stack.
Was This Post Helpful? 0
  • +
  • -

#13 BenedictRM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 24-August 12

Re: Postfix expression evaluation from a file trouble using stacks

Posted 03 October 2012 - 09:45 PM

Good call, I got this to run very well. Thanks for your input everyone!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1