PROJECT 0: PROGRAM TRACE VERIFICATION

Project description
The goals of this project are to:
• brush up on your C++,
• use the stack data structure, which you are familiar with,
• use the STL (Standard Template Library) stack, string, and iostream classes,
• test your program in the command line environment with input/output redirection and diff utilities,
and
• get used to how this course uses the upload site.
When a compiled C++ program executes, it usually starts in the function called main() (though
technically that's just a formality; the name of the starting function can be anything). From there, it
can call another function, say read_input(), which in turn might call another function, such
as istream::operator(), etc. The executing program also returns from each called function, in
the reverse order from the call order. So continuing our example, it must first return
from istream::operator(), then return from read_input(), then return from main().
Conversely, it could not return from read_input() before it had returned from the inner call
to istream::operator().
There are many program analysis tools that allow programmers to examine the behavior of
executing programs. You're probably familiar with debuggers, which allow a programmer to pause an
executing program, examine variables, etc. Valgrind (pronounced "val-grinned") is another tool which
examines executing programs for various problems like memory leaks. Many such tools can operate
on or produce program traces, which describe things like the order of function calls and returns. We
expect traces to be valid, in that every function call has an appropriately matched return from that
function.Here are examples of both valid and an invalid program traces. Both assume that we are starting in
the (unnamed) outermost function (e.g. main()).
Trace 1 is valid, because every function call return in the correct order.

Traces 2-4 are invalid, because:
• Trace 2 returns from read_input() before it returns from istream::operator.
Trace 1 (valid) Trace 2 (invalid) Trace 3 (invalid) Trace 4 (invalid)
call read_input
call
istream::operator

return
istream::operator

call
istream::operator

return
istream::operator

return read_input
call solve
call log
return log
call abs
return abs
call
ostream::operator
<<
return
ostream::operator
<<
return solve
call read_input
call
istream::operator

return
istream::operator

call
istream::operator

return read_input
call solve
call log
return log
call abs
return abs
call
ostream::operator<
<
return
ostream::operator<
<
return solve
call read_input
call
istream::operator

return
istream::operator

call
istream::operator

return
istream::operator

return read_input
call log
return log
call abs
return abs
call
ostream::operator<
<
return
ostream::operator<
<
return solve
call read_input
call
istream::operator

return
istream::operator

call
istream::operator

return
istream::operator

return read_input
call solve
call log
return log
call abs
return abs
call
ostream::operator<
<
return
ostream::operator<
<• Trace 3 returns from solve(), but that function was never called.
• Trace 4 does not return from solve().
Your task for this project is to determine the validity of program traces. You'll be given a trace of an
executing program, and you should determine whether the trace is valid or not. If it's not valid, your
program should describe why.
You will use an STL stack to keep track of called functions. Here is a good algorithm for validating
program traces: For each function called, place the function's name on the stack. When a function
returns, check that its name matches the name on the top of the stack. Finally, at the end of the
trace, check that the stack is empty.
You might want to refer to the STL documentation on the stack and string data types.
Input format
Your program should read from standard input (i.e. cin). It will write to standard output (i.e. cout).
This is the way ALL of our projects will be, unless otherwise indicated.
Each input will consist of one trace. Each line of input will contain either a call or a return,
followed by a space, followed by the name of the function. The name of the function may not contain
whitespace. When comparing two function names to see if they match, case IS important.
Program output
Here are the outputs your program may produce:
Valid trace
Maximum call depth was DEPTH

for valid traces, and the output of
Invalid trace at line LINENUMBER
followed by one of the following:
Returning from FUNCTION1 instead of FUNCTION2
Returning from FUNCTION but no functions are currently being called
Not all functions returned
followed by a stack trace. The difference between the first two errors is whether any functions are on
the stack. See (and use) the executables below for details.Your program should produce only one of these statements per document. In addition, if the trace is
invalid, your program should produce the stack trace (the functions on the stack when the error is
detected), one line per function. If there are multiple errors, print only the first one detected (earliest
in the input). The terms in all-caps are defined as follows:
• DEPTH: the number of items on the stack
• LINENUMBER: the line number of the input (where the error is detected)
• FUNCTION1, FUNCTION2, FUNCTION: names of functions (FUNCTION1 is the function that is
trying to return, while FUNCTION2 is the function on top of the stack)


See below for real examples of program outputs.
Provided code
You should use the .cpp file provided here, modify it appropriately, and upload your solution. You
may modify anything you like, but it has a basic structure you can follow.
• driver-proj0.cpp
Sample executables
Here are sample executables for you which correctly solve this problem. When you design test
cases, you can judge your output against the output from the correct solution. Here is a correct
solution in various compiled formats:
• DOS executable
• Linux (Intel) executable
• MacOSX (universal binary) executable
For each of these, you need to run them from the command-line (i.e. DOS or bash or Terminal.app).
You can't just download them and double-click them to run. Also, for the linux and OSX binaries,
after you've downloaded them you need to make sure that they are executable. To do this, from the
command line type chmod +x file, where file is the name of the program you downloaded.
If you give a command-line argument to these executables, they will print extra information about
how it is processing the input. For example, this will execute the program like normal, redirecting
input from a file called my_input.txt:
% project0_solution_dos.exe < my_input.txt
But here is the mode of operation that will cause the program to print out what it is doing in more
detail:% project0_solution_dos.exe printMore < my_input.txt
The command-line argument doesn't have to be the word "printMore", it can be anything.
Sample input files
Use these sample input files to compare the output of your solution to the correct output. You can get
the correct output by running the input through one of the sample executables. You
should download these input files to your computer (in other words, don't copy and paste), and use
file redirection to redirect the inputs into the sample executable and into your program. You should
also use file redirection to capture the outputs from these programs. Don't use copy/paste, and don't
type things directly into your program. Please read the course pages for a more complete description
of how to test your program, and how to use file redirection..
Please note that you may see the wrong thing if you view these input files in your web
browser — it may interpret the text as HTML, when it should show you plain text. Instead, you
should download them directly to your computer (e.g. right-click on each link and select the
appropriate download option). In general, you should AVOID copy-and-pasting input and output in
this class.
Here are sample executables for you which correctly solve this problem. When you design test
cases, you can judge your output against the output from the correct solution. Here is a correct
solution in various compiled formats:
• input_1.txt
• input_2.txt
• input_3.txt
• input_4.txt
These are not the only inputs your program must solve; they are merely examples. The upload site
will have more tests, to which you do not have access. Therefore, making your own tests is
essential.