?? calc.html
字號:
<html>
<head>
<title>Stack-based Calculator</title>
<meta name="description" content="Reverse Polish notation calculator in C++">
<meta name="keywords" content="top-down, design, calculator, stack, member function, private">
<link rel="stylesheet" href="../../rs.css">
</head>
<body background="../../images/margin.gif" bgcolor="#FFFFDC">
<!-- Main Table -->
<table cellpadding="6">
<tr>
<td width="78">
<td>
<h3>Stack-based calculator</h3>
<p class=topics>
Top down design, make, private member functions, if statement, do/while loop.
<p>
Our next step will be to design and implement a small but useful program using the techniques that we learned so far. It will be a simple stack based calculator. Even though it is a very small project, we will follow all the steps of the design and implementation process. We'll start with the functional specification, then proceed with the architectural design, and finally implement the program.
<h3>Functional Specification</h3>
<p>
The stack-based calculator has a simple interface. It accepts user input in the form of numbers and operators. Numbers are stored in the LIFO type memory--they are pushed on the stack. Binary operators are applied to the two top level numbers popped from the stack, and the result of the operation is pushed on top of the stack. If there's only one number in the stack, it is substituted for both operands. After every action the contents of the whole stack is displayed.
<p>
Since effectively the calculator implements reverse Polish notation, there is no need for parentheses. For simplicity we will implement only four basic arithmetic operations. A sample session may look like this (user input follows the prompt '>'):
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>> 3
3
> 2
3
2
> +
5
> +
10</pre>
</table>
<!-- End Code -->
<h3>Design</h3>
<p>
The obvious top-level object is the <i>calculator</i> itself. It stores numbers in its memory and performs operations on them. Since we would like to be able to display the contents of the calculator's stack after every action, we need access to a stack <i>sequencer</i>. Finally, in order to completely decouple input/output operations from the calculator, we should have an <i>input</i> object that obtains input from the user and does some pre-processing (tokenization) to distinguish between numbers and operators.
<p>We'll use the standard <var>cout</var> object for output.
<p>
The minimum lifetimes of these three objects are the following:
<ul>
<li>The calculator has to be alive during the whole session since it has long term memory.
<li>The scope of the input object is associated with a single input operation.
<li>The scope of the sequencer is associated with every stack display operation that follows a successful calculator action.
</ul>
<p>
The input object obtains a string from the standard input. It can distinguish between numbers and operators, returning different tokens depending on the input. If the token is 'number' the string is converted to an <var>int</var> and the input object remembers its value.
<p>
The calculator object accepts the input object, from which it can get pre-digested data, and executes the command. If the data is a number, it stores it in a stack; if it is an operator, it performs the operation. The results can be viewed by creating a stack sequencer--the calculator may simply give access to its stack for the purpose of iteration.
<p>
Notice that we have only three types of objects interacting at the top level, plus one object, the stack, that we can treat as a black box (we don't call any of its methods, we just pass access to it from one component to another). This is not just a side effect of the simplicity of our project--we should always strive to have only a small number of top level objects.
<p>
Once the top level is established, we can start our top-down descent. In our design we may go one level deeper into the <i>calculator</i> object. We already know that it has a stack. The stack object will thus be embedded in it. We will re-use the stack that we used in the previous paragraph.
<h3>Stubbed Implementation</h3>
<p>
The top-down design will be followed by the top-down implementation. Based on our architectural specification we start to write the <var>main</var> procedure.
<tr>
<td class=margin valign=top>
<a href="source/stubs.zip"><img src="../../images/brace.gif" width=16 height=16 border=1 alt="Download!"><br>source</a>
<td>
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>void <span class=method>main</span> ()
{
Calculator TheCalculator;
bool status;
do
{
// Prompt for input
cout << "> ";
Input input;
status = TheCalculator.Execute (input);
if (status)
{
for (StackSeq seq (TheCalculator.GetStack ());
!seq.AtEnd ();
seq.Advance () )
{
cout << " " << seq.GetNum () << endl;
}
}
} while (status);
}</pre>
</table>
<!-- End Code -->
<p>
We have introduced some new constructs here, the <var>do</var>/<var>while</var> loop and the <var>if</var> statement. The execution of the body of the <i>do</i>/<i>while</i> loop is repeated as long as the condition in the <i>while</i> clause remains true. Notice that, unlike in the case of the <i>for</i> loop, the body of the <i>do</i>/<i>while</i> loop is always executed at least once. As should be obvious by now, the body of the loop forms a separate local scope (even if it is a single statement and the braces are omitted).
<p>
The body of the <i>if</i> statement is entered only if the condition in the <i>if</i> clause is true (different from zero). Otherwise it is skipped altogether. And again, the body of the <i>if</i> statement forms a local scope even if it is only one statement, in which case the braces may be omitted.
<p>
Notice also that the variable <var>status</var> is defined without being initialized. We try to avoid such situations in C++. Here I took the liberty of not initializing it, since it is always initialized inside the body of the <i>do</i>/<i>while</i> loop (and we know that it is executed at least once). I couldn't define the variable <var>status</var> inside the scope of the loop, because it is tested in the <i>while</i> clause which belongs to the outer scope. The <i>while</i> clause is evaluated during each iteration, after the body of the loop is executed.
<p>
Next, following the top-down approach, we'll write stub implementations for all classes. The stack is passed from the calculator to the sequencer and we don't need to know anything about it (other than that it's an object of class <var>IStack</var>). Hence the trivial implementation:
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>class IStack {};</pre>
</table>
<!-- End Code -->
<p>
The sequencer has all the methods stubbed out. I have added to it a dummy variable, <var>_done</var>, to simulate the finiteness of the stack. <var>GetNum</var> returns the arbitrarily chosen number 13.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>class <span class=method>StackSeq</span>
{
public:
StackSeq (IStack const & stack) : _stack (stack), _done (false)
{
cout << "Stack sequencer created\n";
}
bool AtEnd () const { return _done; }
void Advance () { _done = true; }
int GetNum () const { return 13; }
private:
IStack const & _stack;
bool _done;
};</pre>
</table>
<!-- End Code -->
<p>
At this level of detail, the class <var>Input</var> exposes only its constructor:
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>class <span class=method>Input</span>
{
public:
Input ()
{
cout << "Input created\n";
}
};</pre>
</table>
<!-- End Code -->
<p>
The calculator, again, has a dummy variable whose purpose is to break out of the loop in main after just one iteration.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>class <span class=method>Calculator</span>
{
public:
Calculator () : _done (false)
{
cout << "Calculator created\n";
}
bool Execute (Input& input)
{
cout << "Calculator::Execute\n";
return !_done;
}
IStack const & GetStack () const
{
_done = true;
return _stack;
}
private:
IStack _stack;
bool _done;
};</pre>
</table>
<!-- End Code -->
<p>
The method <var>GetStack</var> returns a <var>const</var> reference to <var>IStack</var>. In other words it makes a read-only alias for the calculator's private object <var>_stack</var> and makes it available to the caller. The user may use this alias to access <var>_stack</var>, but only through its <var>const</var> methods, or, if it is an <var>IStack</var>'s friend, by reading the values of <var>_top</var> and those stored in the array <var>_arr</var>. This is exactly what the sequencer needs. Notice also that the statement <var>return _stack</var> is interpreted by the compiler to return a <i>reference</i> to <var>_stack</var>. This is because <var>GetStack</var> was declared as returning a reference. If <var>GetStack</var> were declared as
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>IStack const GetStack () const;</pre>
</table>
<!-- End Code -->
the compiler would return a read-only <i>copy</i> of the stack. Copying the stack is somehow more expensive than providing a reference to it. We'll come back to this problem later, when we talk about value classes.
<p>
With all the dummies in place, we can compile and execute the test program. Its output shows that everything works as expected.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>Calculator created
> Input created
Calculator::Execute
Stack sequencer created
13
> Input created
Calculator::Execute</pre>
</table>
<!-- End Code -->
<h3>Implementation</h3>
<h4>Calculator: Implementation</h4>
<p>
Now is the time to start the top to bottom descent. The first candidate for implementation is the <var>Calculator</var> itself. When implementing the calculator we'll find out what we need from the <var>Input</var> object. Let's start with the <var>Execute</var> method. First, it should retrieve the token from the input. We may expect the following tokens: the number token, any of the arithmetic operator tokens, or the <i>error</i> token. For each type we do a different thing. For the <i>number</i> token we retrieve the value of the number from the input and push it on the stack. For the <i>operator</i>, we pop two numbers (or one if there aren't two), pass them to the <var>Calculate</var> method and push the result.
<tr>
<td class=margin valign=top>
<br>
<a href="source/calc.zip">
<img src="../../images/brace.gif" width=16 height=16 border=1 alt="Download!"><br>source</a>
<td>
<!-- Code -->
<table width="100%" cellspacing=10><tr>
<td class=codeTable>
<pre>bool <span class=method>Calculator::Execute</span> (Input const & input)
{
int token = input.Token ();
bool status = false; // assume failure
if (token == tokError)
{
cout << "Unknown token\n";
}
else if (token == tokNumber)
{
if (_stack.IsFull ())
{
cout << "Stack is full\n";
}
else
{
_stack.Push (input.Number ());
status = true; // success
}
}
else
{
assert (token == '+' || token == '-'
|| token == '*' || token == '/');
if (_stack.IsEmpty ())
{
cout << "Stack is empty\n";
}
else
{
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -