http://www.stroustrup.com/Programming/PPP2code/std_lib_facilities.h
My version is spelt differently so adjust the code accordingly if copying and pasting.
Chapter 6 // Exercise 3
Add a factorial operator: use suffix ! operator to represent "factorial." For example, the expression 7! means 7*6*5*4*3*2*1. Make ! bind tighter than * and /; that is 7*8! means 7*(8!) rather than (7*8)!. begin by modifying the grammar to account for a higher-level operator. To agree with the standard mathematical definition of factorial, let 0! evaluate to 1.
Hint: The calculator functions deals with doubles, but factorial is defined only for ints, so just for x!, assign the x to an int and calculate the factorial of that int.
Sweet baby Jesus and the orphans. I read this and thought "what the hell is a factorial? Is he just making shit up now?". After some researching on factorials it's basically represented like this n(n-1). To start off I wrote a program that works out a factorial and got it working just so I understood what I was working with. Below is the program for documentation purposes:
#include "stdafx.h"
#include "std_lib_facilities_new_version.h"
using namespace std;
int getFactorial(int n)
{
if (n == 0)
n = 1;
int factorial = n;
for (int i = n - 1; i > 1; --i)
{
factorial = factorial*i;
}
return factorial;
}
int main()
{
cout << "Please enter a number to find the factorial:\n";
cout << "Press x to quit.\n";
while (cin)
{
int n;
cin >> n;
int f = getFactorial(n);
cout << n << "!" << " = " << f << endl;
cout << "Please enter a number to find the factorial:\n";
}
keep_window_open();
return 0;
}
The for loop in getFactorial() starts with i assigned -1 of whatever the number you input. So if n was 5, i will equal 4. Factorial is then assigned itself; multiplied by i. So for each iteration, i minuses 1 until it reaches 1 and multiplies with the previous answer.
So now we know how do do a factorial, it's just a matter of implementing it within the calculator program. First I added '!' to the case list in get():
Token Token_stream::get()
{
if (full)
{ // do we already have a Token ready?
// remove token from buffer
Token_stream::full = false;
return buffer;
}
char ch;
cin >> ch; // note that >> skips whitespace (space, newline, tab, etc.)
switch (ch)
{
case '=': // for "print"
case 'x': // for "quit"
case '(': case ')': case '+': case '-': case '*': case '/':
case '{': case '}': case '!':
return Token(ch); // let each character represent itself
case '.':
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
{
cin.putback(ch); // put digit back into the input stream
cin >> val; // read a floating-point number
return Token('#', val); // let '#' represent "a number"
}
default:
error("Bad token");
}
}
Then, I created a new function called int higherTerm() which is obviously higher than term. This is meant to illustrate to the computer that '!' binds tighter than '*' or '/'. This code is placed directly after primary().
int getFactorial(int n) //function that deals with factorials
{
if (n == 0)
n = 1;
int factorial = n;
for (int i = n - 1; i > 1; --i)
{
factorial = factorial*i;
}
return factorial;
}
//------------------------------------------------------------------
//deal with !
int higherTerm()
{
double left = primary();
Token t = ts.get(); // get the next token from token stream
while (true)
{
switch (t.kind)
{
case '!':
{
int ileft = left; //changing the double to an int, this will round down
left = getFactorial(ileft);
t = ts.get();
break;
}
default:
ts.putback(t); // put t back into the token stream
return left;
}
}
}
//------------------------------------------------------------------
// deal with *, /
double term()
{
double left = higherTerm();
Token t = ts.get(); // get the next token from token stream
while (true)
{
switch (t.kind)
{
case '*':
{
left *= higherTerm();
t = ts.get();
break;
}
case '/':
{
double d = higherTerm();
if (d == 0) error("divide by zero");
left /= d;
t = ts.get();
break;
}
default:
ts.putback(t); // put t back into the token stream
return left;
}
}
}
So higherTerm() now gets the primary, the function checks to see if there is a '!' after the primary, if not, passes the number on down the food chain. term() now calls to higherTerm() so it gets whatever has been left over from there.
Here is the full program:
#include "stdafx.h"
#include "std_lib_facilities_new_version.h"
using namespace std;
double val; //global variable
//------------------------------------------------------------------------------
class Token {
public:
char kind; // what kind of token
double value; // for numbers: a value
Token(char ch) // make a Token from a char
:kind(ch), value(0) { }
Token(char ch, double val) // make a Token from a char and a double
:kind(ch), value(val) { }
};
//------------------------------------------------------------------------------
class Token_stream {
public:
Token_stream(); // make a Token_stream that reads from cin
Token get(); // get a Token (get() is defined elsewhere)
void putback(Token t); // put a Token back
private:
bool full; // is there a Token in the buffer?
Token buffer; // here is where we keep a Token put back using putback()
};
//------------------------------------------------------------------------------
// The constructor just sets full to indicate that the buffer is empty:
Token_stream::Token_stream()
:full(false), buffer(0) // no Token in buffer
{
}
//------------------------------------------------------------------------------
// The putback() member function puts its argument back into the Token_stream's buffer:
void Token_stream::putback(Token t)
{
if (full) error("putback() into a full buffer");
buffer = t; // copy t to buffer
full = true; // buffer is now full
}
//------------------------------------------------------------------------------
Token Token_stream::get()
{
if (full)
{ // do we already have a Token ready?
// remove token from buffer
Token_stream::full = false;
return buffer;
}
char ch;
cin >> ch; // note that >> skips whitespace (space, newline, tab, etc.)
switch (ch)
{
case '=': // for "print"
case 'x': // for "quit"
case '(': case ')': case '+': case '-': case '*': case '/':
case '{': case '}': case '!':
return Token(ch); // let each character represent itself
case '.':
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
{
cin.putback(ch); // put digit back into the input stream
cin >> val; // read a floating-point number
return Token('#', val); // let '#' represent "a number"
}
default:
error("Bad token");
}
}
//------------------------------------------------------------------------------
Token_stream ts; // provides get() and putback()
//------------------------------------------------------------------------------
double expression(); // declaration so that primary() can call expression()
int getFactorial(int n);
//------------------------------------------------------------------------------
// deal with numbers and parentheses
double primary()
{
Token t = ts.get();
switch (t.kind)
{
case '{': // handle '{' expression '}'
{
double d = expression();
t = ts.get();
if (t.kind != '}')
error("'}' expected");
return d;
break;
}
case '(': // handle '(' expression ')'
{
double d = expression();
t = ts.get();
if (t.kind != ')') error("')' expected)");
return d;
break;
}
case '#': // we use '#' to represent a number
{
return t.value; // return the number's value
break;
}
default:
error("primary expected");
}
}
//------------------------------------------------------------------------------
int getFactorial(int n) //function that deals with factorials
{
if (n == 0)
n = 1;
int factorial = n;
for (int i = n - 1; i > 1; --i)
{
factorial = factorial*i;
}
return factorial;
}
//------------------------------------------------------------------------------
//deal with !
int higherTerm()
{
double left = primary();
Token t = ts.get(); // get the next token from token stream
while (true)
{
switch (t.kind)
{
case '!':
{
int ileft = left; //changing the double to an int, this will round down
left = getFactorial(ileft);
t = ts.get();
break;
}
default:
ts.putback(t); // put t back into the token stream
return left;
}
}
}
// deal with *, /
double term()
{
double left = higherTerm();
Token t = ts.get(); // get the next token from token stream
while (true)
{
switch (t.kind)
{
case '*':
{
left *= higherTerm();
t = ts.get();
break;
}
case '/':
{
double d = higherTerm();
if (d == 0) error("divide by zero");
left /= d;
t = ts.get();
break;
}
default:
ts.putback(t); // put t back into the token stream
return left;
}
}
}
//------------------------------------------------------------------------------
// deal with + and -
double expression()
{
double left = term(); // read and evaluate a Term
Token t = ts.get(); // get the next token from token stream
while (true) {
switch (t.kind) {
case '+':
left += term(); // evaluate Term and add
t = ts.get();
break;
case '-':
left -= term(); // evaluate Term and subtract
t = ts.get();
break;
default:
ts.putback(t); // put t back into the token stream
return left; // finally: no more + or -: return the answer
}
}
}
//------------------------------------------------------------------------------
void printInstructions()
{
cout << "Welcome to our simple calculator!\n";
cout << "You can use + - / * and ! for factorial \n";
cout << "Press = to print the answer and x to exit.\n";
cout << "Please enter expressions using floating-point numbers:\n" << endl;
}
//------------------------------------------------------------------------------
int main()
try
{
printInstructions();
val = 0;
while (cin)
{
Token t = ts.get();
while (t.kind == '=')
t = ts.get();
if (t.kind == 'x')
{
return 0;
}
ts.putback(t);
cout << expression() << '\n';
}
return 0;
}
catch (exception& e) {
cerr << "error: " << e.what() << '\n';
keep_window_open();
return 1;
}
catch (...) {
cerr << "Oops: unknown exception!\n";
keep_window_open();
return 2;
}
//------------------------------------------------------------------------------
No comments:
Post a Comment