Programming Laboratory V: calculating a string expression with parentheses

Programming Laboratory V:
Calculating a String Expression with Parentheses

Absolutely no copying others' work
Due Dates

Wednesday, December 10, 2008 in class, or
Monday, December 08 or Tuesday, December 09 in labs.

The Objectives
This lab is an extension of the Lab 3. Design and implement C++ and assembly programs which calculate a string expression with parentheses. Students learn how to link assembly procedures to a C/C++ program. This lab is with about 150 lines of assembly code and 60 lines of C++ code.

Submission Methods
Turn in hard-copy C/C++ and assembly code and apply either one of the following two methods:

Post the C/C++ and assembly code at http://people.cs.und.edu/~userid/250/ .
Turn in a CD labeled with your name and lab5 .

The Problem (Calculating a String Expression with Parentheses)
Write a program that calculates a string expression by performing the following tasks:

Scans the input string character-by-character from left to right.
Calculates the string enclosed in parentheses or the final string. A string expression may include two binary operators
- +: string concatenation. For example,
```
     "abc"+"xyz" = "abcxyz"
```
- /: string removal. It removes the first occurrence of the pattern from the string. For example,
```
     "abcxyz"/"cx" = "abyz"
```
  and
```
     "xabyabz"/"ab" = "xyabz"
```
Both operators are left associative and have the same precedence.
If the final string is not reached yet, go back to Step 1. Otherwise, prints the result.

No spaces are allowed in the string expression and no error checking is required, i.e., assume the input is always correct.

The Requirements
The following requirements have to be met:

Have to link assembly-language modules to a C/C++ program.
This lab has to include exactly three files with the exact file names and functions:
- main.cpp, which manages the stack, handles the parentheses, and calls the lab3.asm,
- lab3.h, which is a declaration, and
- lab3.asm, which calculates a string expression without parentheses.

If the requirements are not met exactly, the lab may not execute correctly or the instructors may refuse to grade the lab. Students take a full responsibility for the consequence.

A Suggested Method
A suggested method is outlined as follows:

Push the symbol of start-of-expression ‘$’ to the stack.
Scan the input string byte by byte.
Push everything to the stack until a right parenthesis ‘)’ or the end of the string is reached.
Pop everything from the stack to a temporary string until a left parenthesis ‘(’ or the start-of-string ‘$’ is reached.
Call the procedure of the Laboratory III to calculate the string expression.
If the start-of-expression ‘$’ is reached, then the result string is the final answer. Otherwise, push the result string to the stack and go back to Step 2.

For example, assume that the source string is ("abc"+"xyz")/("c"+"xy"). The final string is calculated as follows (the italic string with a yellow-color background is in the stack):

Push the symbol of start-of-expression ‘$’ to the stack.
```
   $("abc"+"xyz")/("c"+"xy")
```
Read the input string expression character by character and push the characters into a stack until encountering a right parenthesis.
```
   $("abc"+"xyz")/("c"+"xy")
```
Pop the characters from the stack until encountering a left parenthesis or ‘$’.
```
   $/("c"+"xy")
```
Send the string expression "abc"+"xyz" inside the first pair of parentheses to the Lab3 for calculation. Push the result string "abcxyz" back to the stack.
```
   $"abcxyz"/("c"+"xy")
```
Keep reading the string and push the characters into the stack until encountering the next right parenthesis.
```
   $"abcxyz"/("c"+"xy")
```
Pop the characters from the stack until encountering a left parenthesis or ‘$’.
```
   $"abcxyz"/
```
Send the string expression "c"+"xy" inside the second pair of parentheses to the Lab3 for calculation. Push the result string "cxy" back to the stack.
```
   $"abcxyz"/"cxy"
```
Pop the characters from the stack until reaching a left parenthesis or ‘$’.
```
   $
```
Send the final string expression "abcxyz"/"cxy" to the Lab3 for calculation. Push the result string "abz" back to the stack.
```
   $"abz"
```
Pop the characters from the stack until reaching a left parenthesis or ‘$’ and print the final string "abz".

Execution Examples

Examples of Laboratory 5 Execution


C:\250\lab\5\Debug> Project.exe
 
Evaluating a String Expression with Parentheses

Enter a string expressin with parentheses:

    "abc"+"xyz"/"cx"
  = "abyz"
 
 
C:\250\lab\5\Debug> Project.exe 
 
Evaluating a String Expression with Parentheses 
 
Enter a string expressin with parentheses: 
 
    "abc"+("xyz"/"cx") 
  = "abcxyz" 
  
 
C:\250\lab\5\Debug> Project.exe
 
Evaluating a String Expression with Parentheses
 
Enter a string expressin with parentheses:
 
    ("abc"+("xyz"/"x"))/"cy" 
  = "abz"
 

C:\250\lab\5\Debug> Project.exe
 
Evaluating a String Expression with Parentheses
 
Enter a string expressin with parentheses:
 
    ("abc"+"xyz")/("c"+"xy") 
  = "abz" 
 

C:\250\lab\5\Debug> Project.exe
 
Evaluating a String Expression with Parentheses 
 
Enter a string expressin with parentheses: 
 
    ("abcd"/"c")+("wxyz"/"xy")
  = "abdwz"
 

C:\250\lab\5\Debug> Project.exe
 
Evaluating a String Expression with Parentheses
 
Enter a string expressin with parentheses: 
 
    (("abcc"/"c")+"def")/"bcd"
  = "aef"

The italic text with a yellow-color background is entered by users.

A Suggested Procedure and Programming Hints
You may also refer to the Getting Started page from the textbook author.

Copy the folder C:\Irvine\examples\ch12\VisualCPP\FindArray to another folder such as c:\250\lab\5\.
Open the project by picking the project .
In the Solution Explorer window, right click the mouse next to the files and re-name AsmFindArray.asm to lab3.asm and findarr.h to lab3.h, and remove findArr.cpp.
Use this project, a template, as a starting point to write your own programs.

Three programming hints are

The assembly procedures will only set variable values the first time. For example, the definition
```
     op   BYTE  '+'
```
will set the variable op to + only at the first call from C++. The next calls will not re-set the op value.

The C string function strlen( ) will not return the correct length if the string includes double quotes and spaces. For example,
- If str = "a ", then strlen(str) = 2.
- If str = "a", then strlen(str) = 3.
Though this problem can be solved, we simply test only the strings without spaces in order to make the lab simple.

The following command does not work for Visual C++ 2005:
```
     stack[count++] = '\"';
```
You have to define the double quote as a character before using it:
```
     char  dquote = '\"';
     stack[count++] = dquote;
```

About C/C++
The C/C++ knowledge required for this laboratory is minimal. The instructor used about 60 lines for the main.cpp. For a C/C++ tutorial, you may check Programming in C: A Tutorial. The following C/C++ commands may be used in this lab:

No.	Command	Description
1	char	Defining characters
2	cin	The standard input
3	const int	Defining integer constants
4	cout	The standard output
5	extern "C"	C++ linkage declaration
6	for	loop
7	if	if statement
8	#include <iostream>	Input/Output stream class
9	#include <string>	Standard C library to manipulate C strings.
10	return	Stops execution and returns to the calling function.
11	strlen( const char * string );	Returns the number of characters in string before the terminating null-character.
12	unsigned int	Defining unsigned integers
13	using namespace std;	Uses standard namespaces.
14	void	If you do not want to return a value, you must use the return type `void` and miss out the `return` statement.
15	while	loop

The following code is to reverse the string str in place:

   for ( int i=0, j=strlen(str)-1;  i < j;  i++, j-- ) {
      char c = str[i];
      str[i] = str[j];
      str[j] = c;
   }

You may use an array to simulate a stack.

Possible Assembly Instructions Used
The following operators, directives, and commands may be used in this lab:

No.	Operators/ Directives/ Commands	Description	Textbook Page Numbers
1	`.586`	Target processor	409
2	`add`	Addition	87 – 88
3	`BYTE`	Directive of defining byte	66 – 67
4	`cmp`	Performs an implied subtraction of a source operand from a destination operand.	156
5	`.code`	Marks the beginning of the code segment.	55
6	`dec`	Decrement	87
7	`DWORD`	Directive of defining doubleword	68
8	`END`	Marks the last line of the program to be assembled.	59
9	`ENDP`	Marks the end of a procedure.	59
10	`.IF .ELSEIF .ELSE .ENDIF`	`IF` statement	184 – 186
11	`inc`	Increment	87
12	`je`	Jump if equal	158 – 162
13	`jmp`	Causes an unconditional transfer to a target location inside the code segment.	104
14	`jne`	Jump if not equal	158 – 162
15	`loop`	Loop. `ECX` is automatically used as a counter and is decremented each time the loop repeats.	105 – 106
16	`.MODEL flat, C`	Uses the flat memory model and C calling conventions.	246 – 248
17	`mov`	Move	81 – 82
18	`OFFSET`	Returns the offset of a data label.	94
19	`PROC`	Identifies the beginning of a procedure.	59
20	`PROC … USES`	Lists the names of all registers modified within a procedure.	140 – 142
21	`PROTO`	Creates a prototype for an existing procedure.	253 – 255
22	`PTR`	Override the declared size of an operand.	95 – 96
23	`ret`	Pops the return address from the stack into the instruction pointer.	136
24	`sub`	Subtraction	88

Evaluation
The following features will be considered when grading:

This lab will not be graded if the system interface can not be found at http://people.cs.und.edu/~userid/250/ or a CD is not submitted. For security, perform the following operation:
```
  gandalf> chmod 700 lab?.asm* *.cpp *.h
```
to block all read/write accesses from others to the files lab?.asm*, *.cpp, and *.h . Firefox will be used to download code. Be sure your system is working on Firefox 3.0 or above.
Severe penalties will be applied if the Laboratory III procedure is not used.
Microsoft MASM 8.0 assembler will be used to grade labs. Make sure your labs work on MASM 8.0.
Before submitting the lab, test it comprehensively. Absolutely no extra points will be granted after grading.