Slide 13.7: PROTO directive
Slide 14.2: High-level language interface
Home

Programming Laboratory V:
Calculating a String Expression with Parentheses


Absolutely no copying others' work

Due Dates

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:
  1. Post the C/C++ and assembly code at http://people.cs.und.edu/~userid/250/ .
  2. 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:
  1. Scans the input string character-by-character from left to right.
  2. 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.
  3. 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: 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:
  1. Push the symbol of start-of-expression ‘$’ to the stack.
  2. Scan the input string byte by byte.
  3. Push everything to the stack until a right parenthesis ‘)’ or the end of the string is reached.
  4. Pop everything from the stack to a temporary string until a left parenthesis ‘(’ or the start-of-string ‘$’ is reached.
  5. Call the procedure of the Laboratory III to calculate the string expression.
  6. 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):
  1. Push the symbol of start-of-expression ‘$’ to the stack.
       $("abc"+"xyz")/("c"+"xy")
  2. Read the input string expression character by character and push the characters into a stack until encountering a right parenthesis.
       $("abc"+"xyz")/("c"+"xy")
  3. Pop the characters from the stack until encountering a left parenthesis or ‘$’.
       $/("c"+"xy")
  4. 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")
  5. Keep reading the string and push the characters into the stack until encountering the next right parenthesis.
       $"abcxyz"/("c"+"xy")
  6. Pop the characters from the stack until encountering a left parenthesis or ‘$’.
       $"abcxyz"/
  7. 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"
  8. Pop the characters from the stack until reaching a left parenthesis or ‘$’.
       $
  9. Send the final string expression "abcxyz"/"cxy" to the Lab3 for calculation. Push the result string "abz" back to the stack.
       $"abz"
  10. 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.
  1. Copy the folder C:\Irvine\examples\ch12\VisualCPP\FindArray to another folder such as c:\250\lab\5\.
  2. Open the project by picking the project .
  3. 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.
  4. Use this project, a template, as a starting point to write your own programs.
Three programming hints are


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: