Introduction Introduction to Data Structures programming assignments can be comp

Question

Introduction

Introduction to Data Structures programming assignments can be completed either in C++ (preferred) or in Java. In both cases you cannot use libraries or packages that contain pre-built data structures, other than built-in support for objects, arrays, references, and pointers.

Classes in C++ and Java can represent anything in the real world. This assignment is to write a compiler for Z++ programming language.

The Z++ Programming Language

Your program will test if an expression entered by the application user is valid under the Z++ programming language. Therefore, you need to know a little bit about the Z++ programming language (which of course doesn't really exist, not yet anyway).

The Z++ programming language uses only 6 characters, left and right brackets, parentheses and curly braces: { [ ( } ] ). A left curly brace, bracket or parentheses is referred to as a left character. A right curly brace, bracket or parentheses is referred to as a right character.

A Z++ expression is valid if each left character in the expression "matches" with a corresponding right character in the expression. The test for a match requires going left to right through an expression, character by character. When a right character is encountered, then it is compared to the rightmost left character that was not previously compared to a right character. If the characters match, such as { and }, [ and ], or ( and ), then you continue through the expression, comparing each right character to the rightmost left character that was not previously compared to a right character, until either the left and right characters don't match (which means the expression is not valid) or there are no more right characters. When there are no more right characters, if all of the left characters have previously been compared to a right character, the expression is valid. However, if there still are left characters that have not previously been compared to a right character, the expression is invalid.

Let's look at some examples. The following expressions are valid:

[]{}()

{([])}

()[{}]

[{}()]

Note that the matching may be by the right character immediately following the left character, by nesting, or by a combination of the two.

However, the expression [({})) is not valid as [ does not correspond to ). Additionally, the expression ([{}()] is not valid. Even though each right character is matched by a left character, the first left character is left over after you have run out of right characters.

Program Description

Your program, which will be written in C++, not Z++, will prompt the user to enter a string of not more than 20 characters. You may use a character array, a C-string or the C++ string class; the choice is up to you. You can assume the user enters no more than 20 characters (though the user may enter less than 20 characters) and the characters entered are limited to left and right brackets, parentheses and curly braces; you do not need to do any error-checking on this. After the user ends input, by the Enter key, the program checks if the string is a valid Z++ expression, and reports that it either is or isn't. Sample outputs:

Enter an expression: []{}()

It's a valid expression

Enter an expression: ()[{}]

It's a valid expression

Enter an expression: [({)}]

It's NOT a valid expression

Stack Class

Module #3, which accompanies this assignment, explains a stack and how it will be represented by aclass having the member variables and member functions (including a constructor) appropriate for a stack.

Multiple Files

The class will be written using header and implementation files. Your program also will include adriver file, so your multi-file project will have three files:

Module #3 gives you the test.cpp file and all the information necessary to write the cstack.h file. Your job is to write the cstack.cpp file. All class members (variables and functions) must be privateunless they need to be public.

Next is partial code for the header file for the stack class. The code is a bold type and my annotations, contained in code comments, are italicized.

// cstack.h, the code for specification file for stack class

class CStack {

/*

class is a keyword telling C++ a class is being defined.

CStack is the name of the class. Any legal name will do,

though the name should describe the class. The open curly

brace starts the body of the class, just as it does a structure

*/

public:

/*

Public is keyword meaning accessible from outside the class.

Class members, whether variables or functions, are private

unless specifically declared otherwise. The following member

functions are public, so the public keyword is necessary

*/

/*

Now we start defining the member functions.

Note that they are prototypes only; none have a body.

The body is supplied in the implementation file

*/

CStack();    // Constructor. Always public

bool IsEmpty();  // this function could be private

bool IsFull();      // ditto

// here you would continue to define (prototype) the additional member functions

private:

/*

Private is a keyword meaning not accessible from outside the class.

Member variables almost always are private.

Next, the member variables are declared

*/

int top;

char data[21];

};

/*

The close curly brace and semicolon mark the end of the class body,

just as they do with a structure

*/

Next is partial code for the implementation file for the stack class. Once again, the code is a bold type and my annotations, contained in code comments, are italicized.

// cstack.cpp, the code for implementation file for stack class

#include "cstack.h"

/*

You need to include cstack.h to supply the prototypes.

You also may need to include standard header files such as

iostream if your implementation of the member functions

use standard library functions such as cin and cout

*/

bool CStack::IsEmpty ()

{

// code goes here. You didn't think I'd give it away?

}

/*

This is the same IsEmpty function that was prototyped in cstack.h.

The difference is the insertion before IsEmpty of CStack, which is the name

of the class of which IsEmpty is a member, and ::, the scope resolution operator.

This insertion specifies that IsEmpty is a member of the class whose name precedes

the scope resolution operator (CStack). Without CStack:: the compiler would

assume IsEmpty is just a regular function that does not belong to any class.

*/

/*

here you would continue to implement the other member functions

prototyped in cstack.h, including the constructor.

*/

Below is partial code (I'm not going to give it all away) for the driver file. As before, the code is a bold type and my annotations are italicized.

// test.cpp, the code for driver file

#include "cstack.h"

#include <iostream>

#include <cstring>
using namespace std;

/*

You need to include cstack.h because the driver file refers to the CStack class.

You also need need to include standard header files iostream and cstring because

the driver file uses standard library functions such as cin and cout and C-string functions also

*/

bool isValidExpression (CStack&, char*);

/*

This is the prototype of a function implemented later in this file

(this function is not a member function of any class) that determines

if the expression that is its second parameter is a valid G++ expression

and returns true if the expression is valid, false otherwise. This determination

is made using the CStack class, an instance of which is the first parameter.

That parameter is declared by reference but also could be declared by value.

*/

int main (void)    // The driver file has the main function
{

char expression[21];    // allocate memory for user string input

cout<< "Enter an expression: ";
cin >>expression;

CStack stack1;    // creates an instance of a stack (stack1) using class constructor

if (isValidExpression (stack1, expression))

/* This calls the isValidExpression function (which you still need to write) to

fill the data array of the stack. The parameter is the stack instance stack1 */

cout << " It's a valid expression";
else
cout << " It's NOT a valid expression";

return 0;
}

/* This ends the main function. Now we (you) have

to write the isValidExpression function. I'll give you

the function header, and then some hints. */

bool isValidExpression (CStack& stackA, char* strExp)

{

// code goes here

}

// end of driver file

File Name Purpose cstack.h Header file for stack cstack.cpp Implementation file for stack test.cpp Driver file

Explanation / Answer

cstack.h :
Added two methods - push and pop to this class definition.

-------------------------------------------------

cstack.cpp

-------------------------------------------------------

test.cpp:

  class CStack {    /*    class is a keyword telling C++ a class is being defined.    CStack is the name of the class. Any legal name will do,    though the name should describe the class. The open curly    brace starts the body of the class, just as it does a structure    */    public:    /*    Public is keyword meaning accessible from outside the class.    Class members, whether variables or functions, are private    unless specifically declared otherwise. The following member    functions are public, so the public keyword is necessary    */    /*    Now we start defining the member functions.    Note that they are prototypes only; none have a body.    The body is supplied in the implementation file    */        CStack();    // Constructor. Always public        bool IsEmpty();  // this function could be private        bool IsFull();      // ditto        char pop();        void push(char ch);    private:    /*    Private is a keyword meaning not accessible from outside the class.    Member variables almost always are private.    Next, the member variables are declared    */        int top;        char data[21];    };

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.