Part I In this lab, you are to write a program that test if a sequence of words

Question

Part I
In this lab, you are to write a program that test if a sequence of words in a file is “mirrored”, that
is, the second half of the list is the mirrored image of the first half.
For example, a word list of “aa bb bb aa” is mirrored, so is the list of “11 22 01 22 11”.
However, the list “aa bb cc aa” is not.
In fact, if you read the list forward or backward, the results are the same. So the solution is similar
to the one that checks if a string is a palindrome or not.
While you can read all the words from the file to the array and then check the content using a
loop (an iterative approach) , the solution is not elegant, since you don’t know how big the array
should be.
The problem can easily be solved using recursion. If you think recursively, you will realize that if
the entire word list is mirrored, the first word and the last word should be the same, and the
remaining words in the middle should be mirrored. The recursion reads the file sequentially only
once and never need to store the words to an array.
To simply the problem, let’s assume the first element in the file is an integer number that
indicates the number of words in the file. The rest of the file contains the list of the words. For
example, the following is the content of a file with five words:
5 aa bb cc dd ee
Your program will read the file, and display a line of information indicating if the word list is
mirrored or not.

Part II
Here you are to expend the recursive program developed in part one. Your program will not only
test the list to see if it is mirrored or not, it will also print of the words using the following rules,
while the list is been checked.
(1) It will print out the word in the middle of list first in a line, if the list contains an odd
number of words. Note the line will contain only this word.
(2) If the list contains an even number of words, there will be no “middle” word, so the
program prints nothing.
(3) After step 1 or 2, the program prints out the two words that surrounds the middle word or
middle point, in a separate line.
(4) It then prints out the next two “outer” words, and repeats the steps, until all the words are
printed.
Finally the program display whether the list is mirrored or not.
For example, if the word list is aa bb cc dd cc bb aa, the output on the screen would
look like:
dd
cc cc
bb bb
aa aa
Yes, the list is mirrored.
And if the word list is aa bb cc dd dd cc bb AA, the output on the screen would look
like:
dd dd
cc cc
bb bb
aa AA
No, the list is not mirrored.
Note: your code should read the file from beginning to end once and only once, and you should
not use any array. You don’t have to rewrite the program. A few relatively simple modifications
to the recursive code develop in Part I will do the trick.

Part III
When you write you C++ program, you ask the compiler to compile your code, check for errors,
and generate binary code. The compiler is a very complex and powerful piece of software. Think
about it, the complier can analyze very complex C++ source code files and find errors --- many of
the errors are hard for human to detect!
You will learn how to write simple compilers in the Compiler Theory course in the future.
However, in this lab, you can still try to write an extremely simple “compiler”, which checks if a
give source code is grammatically correct or not. Your program does not generate any binary
code. If the source code is correct, you just display “Good, the program has not syntax error.”
Otherwise, it will display “The program contains error(s).”
When you run the “compiler”, it will ask for a source code file name. Once a filename such as
“sample.zpp” is entered by the user, the compiler will read the file, check for errors, and display
the above mentioned messages.
Of course, there is no way you can write a compiler for C++ language (or any real world
programming language) at this stage. Instead, let’s develop a fictional “programming language”
called ZPP (Z Plus Plus). The syntax for ZPP is extremely simple, and the rules are listed as
follows:
(1) The source code contains only one statement and the compiler will only check this
statement. Any extra characters after the statement will be ignored.
(2) The language is “free-form”, like C++, so you can insert any amount of white space
between keywords and/or other symbols.
(3) There only three kind of statements in the language: while statements , if statements, and
empty statements.
(4) An empty statement is any number of white space followed by a “;”
The following is an example of an empty statement:
;
(5) A while statement starts with a keyword “while”, followed by one of the following
a. An empty statement
b. A pair of braces (“{“ and “}”). In the middle of the pair, there must be one and
only one legal ZPP statement (empty, while, or if).
(6) A if statement starts with a keyword “if”, followed by some space, and then a pair of
“()”, and one of the following
a. An empty statement
b. A pair of braces (“{“ and “}”). In the middle of the pair, there must be one and
only one legal ZPP statement (empty, while, or if).
Note: there is not space between “(“ and “)”, so “()” is legal and “( )” is illegal.
(7) The keywords are case sensitive and must be in lower case letters.
(8) There must be some white space between keywords and symbols.
For example, the following is illegal, since there is not space between “while” and “;”.
while;
and the following is also illegal, since there is no space between “{“, “;” and “}”
while
{;}
The following are some examples of legal, correct statements or programs:

1) while ;

2) while
   {
        ;
   }
3) while
   {
       while ;
   }
4) while
   {
       while
       {
         if () ;
       }
   }
5)while
  {
      while
  {
      if ()
  {
      while ;
    }
  }
}
And the following are some illegal statements:
-No space between keywords or symbols:

while;

if ();

-Wrong keyword:

WHILE

{

;

}

-Must have one and only one statement between { }

-while

{

}

Wrong syntax

while

while ;

while

{

if () ;

Can you write the compiler for our ZPP language? Seems like a daunting task, right? Actually,

while the problem is certainly not trivial, it is within the capability of many of you. Like all

programming languages, our ZPP’s grammar definitions are recursive, so it is nature to use

recursion to implement the compiler --- in fact, real compilers heavily depend on recursions!

 

Explanation / Answer

#include NAMESPACE_UPP TextCtrl::TextCtrl() { Unicode(); undosteps = 10; Clear(); undoserial = 0; incundoserial = false; undo_op = false; WhenBar = THISBACK(StdBar); charset = CHARSET_UNICODE; color[INK_NORMAL] = SColorText; color[INK_DISABLED] = SColorDisabled; color[INK_SELECTED] = SColorHighlightText; color[PAPER_NORMAL] = SColorPaper; color[PAPER_READONLY] = SColorFace; color[PAPER_SELECTED] = SColorHighlight; processtab = true; processenter = true; nobg = false; } TextCtrl::~TextCtrl() {} void TextCtrl::MiddleDown(Point p, dword flags) { if(IsReadOnly()) return; if(AcceptText(Selection())) { WString w = GetWString(Selection()); selclick = false; LeftDown(p, flags); Paste(w); Action(); } } void TextCtrl::CancelMode() { selclick = false; dropcaret = Null; isdrag = false; } void TextCtrl::Clear() { cline = cpos = 0; total = 0; line.Clear(); line.Shrink(); ClearLines(); line.Add(); InsertLines(0, 1); DirtyFrom(0); anchor = -1; cursor = 0; SelectionChanged(); Refresh(); undo.Clear(); redo.Clear(); ClearDirty(); SetSb(); PlaceCaret(0); } void TextCtrl::DirtyFrom(int line) {} void TextCtrl::SelectionChanged() {} void TextCtrl::ClearLines() {} void TextCtrl::InsertLines(int line, int count) {} void TextCtrl::RemoveLines(int line, int count) {} void TextCtrl::PreInsert(int pos, const WString& text) {} void TextCtrl::PostInsert(int pos, const WString& text) {} void TextCtrl::PreRemove(int pos, int size) {} void TextCtrl::PostRemove(int pos, int size) {} void TextCtrl::RefreshLine(int i) {} void TextCtrl::InvalidateLine(int i) {} void TextCtrl::SetSb() {} void TextCtrl::PlaceCaret(int newcursor, bool sel) {} void TextCtrl::CachePos(int pos) { int p = pos; cline = GetLinePos(p); cpos = pos - p; } void TextCtrl::Load(Stream& s, byte charset) { Clear(); line.Clear(); ClearLines(); String ln; total = 0; SetCharset(charset); if(charset == CHARSET_UTF8_BOM && s.GetLeft() >= 3) { int64 pos = s.GetPos(); byte h[3]; if(!(s.Get(h, 3) == 3 && h[0] == 0xEF && h[1] == 0xBB && h[2] == 0xBF)) s.Seek(pos); charset = CHARSET_UTF8; } while(!s.IsEof()) { int c = s.Get(); if(c == ' ') { WString w = ToUnicode(ln, charset); line.Add(w); total += w.GetLength() + 1; ln.Clear(); ln.Reserve(1000); } if(c >= ' ' || c == ' ') ln.Cat(c); } ln.Shrink(); WString w = ToUnicode(ln, charset); line.Add(w); total += w.GetLength(); InsertLines(0, line.GetCount()); Update(); SetSb(); PlaceCaret(0); } void TextCtrl::Save(Stream& s, byte charset, bool crlf) const { if(charset == CHARSET_UTF8_BOM) { static byte bom[] = { 0xEF, 0xBB, 0xBF }; s.Put(bom, 3); charset = CHARSET_UTF8; } charset = ResolveCharset(charset); for(int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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