Google Answers Logo
View Question
 
Q: C++ Programing ( Answered 4 out of 5 stars,   0 Comments )
Question  
Subject: C++ Programing
Category: Computers > Programming
Asked by: purplepit-ga
List Price: $50.00
Posted: 03 May 2003 17:26 PDT
Expires: 02 Jun 2003 17:26 PDT
Question ID: 199021
Can you help to write a C++ program, this compiles and runs without
errors, following the below mentioned specification......
********************************************************************************

Part 1
Write a short program to do the following:

·       read in 5 names and push each onto a stack

·       display the stack (see displayStack() in the notes)

·       pop each name from the stack, displaying the stack after each
name is removed

Part 2
Using the function

string infixToPostfix(string infixStr )

as given in the notes (and other functions and data types) complete a
short test program for the function. Use get_line() to read an input
expression (unless you can provide something better). Include a test
plan and several sets of test data. e.g

Enter an infix expression: 3+4

Postfix for [3+4] is: 3 4 +

Infix Expected rpn Infix result rpn result

3+4 3 4 + 7 7

etc.

Note that the arithmetic operators must be added (only the + operator
is in the given code). Note also that the rpn result in the last
column is calculated by hand (for this part).

Part 3
Complete a program that 1)allows the user to enter an infix expression
as a string (use get_line() if you can't find anything better),
2)converts the infix to postfix and 3)evaluates the postfix. This is
basically putting exercise 1 together with the rpn() routine given in
the notes and adding a bit of user interface.

A sample run is given here:

Enter a valid infix expression (<return>

to halt): 5+(4 * 3 - 2)/3 + 6

Infix format : 5+(4 * 3 - 2)/3 + 6

Postfix format : 5 4 3 * 2 - 3 / 6 + +

[ 5 4 3 * 2 - 3 / 6 + + ] evaluates to 14

You should of course include several sets of carefully chosen (and
tested) test data.

Part 4 (an additional exercise you can do to catch up if you missed
some earlier exercises)
If you look at the code for the rpn() function you will see I have
include a possible power() function. The result of power(2,3) would be
8 (i.e. 2 to the power 3). The power() function has a very high
priority (above * and / ). A possible implementation of the power()
function is

int power(int a, int b)

{

  assert (b >= 0) ;

. int result = 1 ;

. for (int i=0; i<b; i++)

. {

.   result *= a ;

. }

. return result ;

}

Extend the infixToPostfix() function (quite a bit to do – the operator
type also needs to be extended etc.) so that the whole things includes
the 'power' notion. The '^' character is used as the 'power' operator.
Thus the infix expression

3 ^ 2 * (4 + 2)

should evaluate to 54
*******************************************************************************
 PLEASE NOTE!!!! the following example code fragments have been given
as a guide to help POSSIBLY!!!!

1)
int rpn(string e, bool& ok, bool trace ) 
// Pre: e contains a valid (?) RPN expression
// Post: returns value of Reverse Polish
// Notation e. ok is false if e not a valid RPN
// expression.

{
   stack<int> s;
   ok=true; // default
   string::iterator it = e.begin();

   while (it != e.end()) // test end of string
   {
      if (isdigit(*it)) // start reading numeric
      {
         int val=*it-'0'; // convert to numeric
         // and read rest of digits:
         it++;
         while (isdigit(*it))
         {
            // add next digit
            val = val*10 + *it - '0'; 
            it++;
         }
         s.push(val);
         // need to read last character again:
         it--;
         
         // display - just for interest
         if (trace)
         {
            cout << "Operation push data: ";
            displayStack(s);
         }
      }
      else // not part of an integer
      {
         if (*it=='*' || *it=='-' || *it=='+' 
             || *it=='/' || *it == '^')
         {
            if (s.size() < 2) 
            {
              // error - stack underflow 
              //(invalid expression)
               ok=false;
               return -1; 
            }
            int right = s.top();
            s.pop();
            int left = s.top();
            s.pop();
            int result;
            switch (*it)
            {
            case '+':
               result = left + right;
               break;
            case '-':
               result = left - right;
               break;
            case '*':
               result = left * right;
               break;
            case '/':
               result = left / right;
               break;
            case '^':
               result = power(left,right);
               break;
            }
            s.push(result);
            if (trace)
            {
               // display - just for interest
               cout << "Operation " << *it 
                    << "        : ";
               displayStack(s);
            }
         }
         else ; // ignore the character
         
      }
      it++; // next character
   }
   if (s.size() == 1) // we have an answer
   {
      return s.top();
   }
   else // there is an error
   {
      ok=false;
      return -2; // error invalid expression
   }
}

2)
string infixToPostfix(string infixStr)
{ 	
	stack < operators > opStack;
	string result("");
	string::iterator it = infixStr.begin() ;
	
	while (it != infixStr.end()) 
	{
		if (isdigit( *it ) ) // process numerics
		{   
			while (isdigit(*it)) 
			{
				result += *it;
				it++;
			}
			result += " ";	// add separator
		}  
		else
		{
			switch(*it++) 
			{	// process other characters
            case '(': 
				opStack.push(leftparen); 
				break;
            case '+': processOp(plusOp, opStack, result);
				break;
            case '-': processOp(minusOp, opStack, result);
				break;
            case '*': processOp(multiplyOp, opStack, result);
				break;
            case '/': processOp(divideOp, opStack, result);
				break;
            case ')':
				while (opStack.top() != leftparen) 
				{
					result += opString(opStack.top());
					opStack.pop();
				}
				opStack.pop();	// pop off left paren
				break;
			}
		}
	}
	while (! opStack.empty()) 
	{	// empty the stack on end of input
		result += opString(opStack.top());
		opStack.pop();
	}
	
	return result;	// return result string
}

3)

template<class T> void displayStack(stack<T> s)
// stacks are not really designed for this!
// the function works on a copy of the original!
{
   // create a reversed stack 
   // - because it looks better!
   stack<T> s2;
   while (!s.empty())
   {
      s2.push(s.top());
      s.pop();
   }
   
   // now display it
   cout << "Current stack: ";
   while (!s2.empty())
   {
      cout << s2.top();
      s2.pop();
      if ( !s2.empty() )  cout << ", " ;
   }
   cout << endl;
}


Thank you........

Request for Question Clarification by dogbite-ga on 03 May 2003 19:09 PDT
Hi purplepit-ga,

  Wow, there are several steps there!

  I would do this now for $100.  Maybe another 
  researcher will want to answer for $50 though.

               dogbite-ga

Request for Question Clarification by aditya2k-ga on 04 May 2003 01:01 PDT
Hi,

You might want to split this into separate questions. (Each part as
one question). That way, you will get quicker responses.

Cheers,
Aditya.

Request for Question Clarification by dogbite-ga on 04 May 2003 08:07 PDT
Responding to aditya2k-ga, the difficulty 
of splitting it up is some of the parts 
depend on subsequent parts.  I think the
best thing is to either wait for somebody
to answer at $50 or raise the offer.

          dogbite-ga

Clarification of Question by purplepit-ga on 04 May 2003 15:37 PDT
Hi dogbite.ga

OK $100 it is, as I really need to do this, how do I go about this, do
I have to post the question again, with the revised amount?

Anthony

Request for Question Clarification by dogbite-ga on 04 May 2003 15:50 PDT
Hi purplepit-ga,

  Just put $50 in the "tip" box when
  you rate the question.  When do you
  need the answer by?

         dogbite-ga
Answer  
Subject: Re: C++ Programing
Answered By: dogbite-ga on 04 May 2003 23:40 PDT
Rated:4 out of 5 stars
 
Hi purplepit-ga,

  I wrote and tested all of the code
  and put it here:

http://nms.lcs.mit.edu/~gch/google/postfix.tar.gz

  Instructions on how to compile and run
  the programs are at the top of their files.

  Please let me know how it works out.

                dogbite-ga

Request for Answer Clarification by purplepit-ga on 05 May 2003 10:46 PDT
Hi again,

I can only seem to access the infixToPostfix.h, and stringstack.h, but
nothing else or any instrutions on how to run or compile!!!
can you please dogbite-ga

thanks

Clarification of Answer by dogbite-ga on 05 May 2003 10:58 PDT
Hi purplepit-ga,

  Sure, I will help you -- I don't totally 
  understand the problem though.  Are you 
  saying the postfix.tar.gz file you downloaded 
  only contained two header files?  I just 
  tried downloading the file and everything
  was there.

  I have put all the files here:

http://nms.lcs.mit.edu/~gch/google/postfix/

  Please go into that directory and download
  each of the files individually.  The instructions
  are at the top of the .cc files.  For example:

//////////////////////////////////////////
// File: pushnames.cc
// Date: 05/05/2003
// Notes: A simple program to read in 5 names
//        from standard in and put them on the
//        stack.  Then pop them all off, displaying
//        the stack each time.  (Part 1)
//
//        To compile:
//
//     g++ -o pushnames pushnames.cc stringstack.o
//
//        To run:
//
//     pushnames
//
//////////////////////////////////////////

  Please let me know if that works for you.

                   dogbite-ga

Clarification of Answer by dogbite-ga on 05 May 2003 14:04 PDT
Hey purplepit-ga,

  Were you able to retrieve the 
  files successfully?

         dogbite-ga

Request for Answer Clarification by purplepit-ga on 08 May 2003 11:46 PDT
Hi dogbite, I tried running this today on Unix and got the initial
error message saying "strihgstack.o not found!!!" and having said
that, I couldn't find the code for it in the downloaded files!!
In addition to this I am using the g++ compiler, but to run we use
/a.out, will this still work? and can you help! or possibly modify the
code for use with visual c++

even if you only manage say parts one and two!!!!!
Thanks
Purplepit-ga

Clarification of Answer by dogbite-ga on 08 May 2003 12:01 PDT
Hi purplepit-ga,

  I don't totally understand what went
  wrong.  Can you please paste exactly
  what you typed into the UNIX prompt
  and exactly what the error message was?

               dogbite-ga

Request for Answer Clarification by purplepit-ga on 08 May 2003 13:43 PDT
Hi ,

Firsty I used an emacs editor to create all the programs, and then
when trying to run the program that included the "stringstack.o" think
it was "pushnames.cc"(am at home now so am not using unix, the error
was I think "stringstack.o no such file or directory"
will be willing to give you another good tip if you can help.....

Purplepit-ga

Clarification of Answer by dogbite-ga on 08 May 2003 14:08 PDT
Hi purplepit-ga,

  I'm sorry.  You first need to type

g++ -o pushnames pushnames.cc stringstack.cc

  to compile the pushnames executable.
  The other compilation instructions
  look like they will work just fine.

  Please let me know how it works for you.

           dogbite-ga

Request for Answer Clarification by purplepit-ga on 09 May 2003 10:07 PDT
Hi dogbite-ga
It's me again, I but you wished you never attempted this question!!
Anyway it still doesn't seem to work!! too many errors to even
contemplate ploughing through, maybe it's got something to do with the
system we use to run programs on, I really dont know.

What I need as a last ditch attempt to get at least some output, is a
visual c++ program(.cpp) for just the first part!! if you could modify
you're program to do the same thing as is required, it would be much
appreciated.

Purplepit-ga

Clarification of Answer by dogbite-ga on 09 May 2003 10:36 PDT
Hi purplepit-ga,

  I do not have Visual C++, so I cannot
  provide that program.  Also, there is
  nothing special about the code -- no
  special libraries or anything that I
  know of -- so it should compile on
  your Visual C++ system just fine.

  It's possible that I could help you
  get it running on your linux machine.
  Can you paste part of the error?

  Also, here is an example execution 
  of the pushnames program:

$ ./pushnames
Enter a name:
Alice Apple
Enter a name:
Bob Bear
Enter a name:
Chris Creame
Enter a name:
Dan Delicious
Enter a name:
Fatty Frank
The Stack
5: Fatty Frank
4: Dan Delicious
3: Chris Creame
2: Bob Bear
1: Alice Apple

The Stack
4: Dan Delicious
3: Chris Creame
2: Bob Bear
1: Alice Apple

The Stack
3: Chris Creame
2: Bob Bear
1: Alice Apple

The Stack
2: Bob Bear
1: Alice Apple

The Stack
1: Alice Apple


                  dogbite-ga
purplepit-ga rated this answer:4 out of 5 stars and gave an additional tip of: $50.00
Thank you!!!

Comments  
There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy