C++

Forum

 
Help with Factorial

Joe C (11)
I'm trying to do the following exercise from Programming: Principles and Practices Using C++ 2Ed.

Ch6 Ex3

Add a factorial operator: use a 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 standard mathematical definition of factorial, let 0! evaluate to 1. Hint: The calculator functions deal with doubles, but factorial is defined only for ints, so just for x!, assign x to an int and calculate the factorial of that int.

Prior to this question I had to clean up some errors and add the use of { and } along with ( and ), so the following code reflects those changes.

This is done within Visual Studio 2017. Grammar outline is after code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
 
// Chapter 6
//

#include "stdafx.h"
#include "std_lib_facilities.h"

class token  // Creating a new class called token
{            // The token is a character/value pair
public:
	char kind;
	double value;
	token(char ch)
		:kind(ch), value(0) {}
	token(char ch, double val)
		:kind(ch), value(val) {}
};

class token_stream  // Creating a new class called token_stream
{                   // This is where token info can be pulled from
public:             // and put back as needed
	token_stream();
	token get();
	void putback(token t);
private:
	bool full;
	token buffer;
};

token_stream::token_stream()        // token_stream function is a member of
	:full(false), buffer(0) {}  // token_stream class

void token_stream::putback(token t) // putback() function is a member of
{                                   // token_stream
	if (full) error("Can't put back into a full buffer");
	buffer = t;
	full = true;
}

token token_stream::get()         // get() function is a member of token_stream
{                                 // and returns a token
	if (full)
	{
		full = false;
		return buffer;
	}

	char ch;
	cin >> ch;

	switch (ch)
	{
	case '=':
	case 'x':
	case '{': case '}': case '(': case ')': case '+': 
        case '-': case '*': case '/': case '!':
		return token(ch);
	case '.':
	case '0': case '1': case '2': case '3': case '4':
	case '5': case '6': case '7': case '8': case '9':
	{
		cin.putback(ch);
		double val;
		cin >> val;
		return token('8', val);
	}
	default:
		error("Bad token");
	}
}

token_stream ts;      // Declare a new token_stream named ts

double expression();  // Declare a new function named expression()

double primary()      // Function deals with brackets or
{                     // Swaps the character out for it's value
	token t = ts.get();
	switch (t.kind)
	{
	case '{':
	{
		double d = expression();
		t = ts.get();
		if (t.kind != '}') error("'}' expected");
		return d;
	}
	case '(':
	{
		double d = expression();
		t = ts.get();
		if (t.kind != ')') error("')' expected");
		return d;
	}
	case '8':
		return t.value;
	default:
		error("Primary expected");
	}
}

double factorial()  // Factorial function that's not working
{
	double left = primary();
	token t = ts.get();
	while (true)
	{
		switch (t.kind)
		{
		case '!':
		{
			int x = left;
			if (x == 0) { left = 1; }
			else if (x < 0) error("Factorial must be a positive integer");
			else for (; x > 0; x--)
			{
				x *= x;
				left = x;
			}
                        t = ts.get();
			break;
		}
		default:
			ts.putback(t);
			return left;
		}
	}
}

double term()  // Function deals with multiplication and division
{
	double left = factorial();
	token t = ts.get();
	while (true)
	{
		switch (t.kind)
		{
		case '*':
			left *= factorial();
			t = ts.get();
			break;
		case '/':
		{
			double d = factorial();
			if (d == 0) error("Can't divide by 0");
			left /= d;
			t = ts.get();
			break;
		}
		default:
			ts.putback(t);
			return left;
		}
	}
}

double expression()  // Function deals with addition and subtraction
{
	double left = term();
	token t = ts.get();
	while (true)
	{
		switch (t.kind)
		{
		case '+':
			left += term();
			t = ts.get();
			break;
		case '-':
			left -= term();
			t = ts.get();
			break;
		default:
			ts.putback(t);
			return left;
		}
	}
}

int main()
try {
	double val = 0;

	cout << "Welcome to our simple calculator.\n"
		<< "Please enter expressions using floating-point numbers.\n"
		<< "Note: Only +, -, *, /, (, ), { and } can be used in the expressions.\n"
		<< "Hint: Use = at the end of an expression to get the result and use x at any time to quit.\n"
		<< "Example: {2+(2+3-1)}*2/1=\n"
		<< '\n';

	while (cin)
	{
		token t = ts.get();
		if (t.kind == 'x') break;
		else if (t.kind == '=')
			cout << "= " << val << '\n';
		else
			ts.putback(t);
		val = expression();
	}
	keep_window_open();
	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;
}


The grammar is as follow;

Expression:
Term
Expression "+" Term
Expression "-" Term
Term:
Factorial
Term "*" Factorial
Term "/" Factorial
Factorial:
Primary
Integer "!"
Primary:
Number
"(" Expression ")"
Number:
Floating-point-literal

So the order in which the functions call upon each other is;

Main -> Expression -> Term -> Factorial -> Primary

I know that the factorial() function is mostly working. It will correctly call upon information from primary(). It will correctly give me 1 when I input 0!. It'll give me the error when I input a negative number (eg. -2!). It just doesn't work right with any positive integer other than 1. I tried some numbers and get the following;

-2! = Factorial must be a positive integer (works)
0! = 1 (works)
1! = 1 (works)
2! = -2.1478e+09 (problem)
4! = -1.77744e+09 (problem)
7! = -1.65649e+09 (problem)

I've been at it for hours and this is the closest I've got it to work. Any help would be greatly appreciated.

Thank You.
ne555 (10692)
line 114, `x' is the number that you want to compute its factorial
`left' is the result.
1
2
3
4
5
 
for (; x > 0; x--)
{
	x *= x; //¡¿?!
	left = x;
}
get pencil and paper and do a desk test
edit: it seems to be called desk check. run the code manually, line by line and write the values that `x' takes.
suppose that at the start x=4


also, ¿why your functions don't recibe a parameter?
Last edited on
Joe C (11)
Thanks for the reply. I was out of town (and away from my computer) for the weekend so I basically thought it over and over. Manually tracking various inputs through the code line by line is basically how I narrowed the issue to the part you pointed out.

I got it to work by changing the code to the following.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
double factorial()
{
	double left = primary();  // I knew this worked by using equations with brackets
	token t = ts.get();
	while (true)
	{
		switch (t.kind)
		{
		case '!':
		{
			int x = left;
			if (x == 0) { x = 1; }  // I tested this and knew it worked
			else if (x < 0)  // I tested this and knew it worked
			{
				error("Factorial must be a positive integer"); keep_window_open();
			}
			else for (int y = x - 1; y > 0; --y)  // So this is where the error was
			{ 
				x = x * y; 
			}
			t = ts.get();
			double left = x;
			ts.putback(t);
			return left;
		}
		default:
			ts.putback(t);
			return left;
		}
	}
}


I needed to convert the double to an int such that an input of 3.4! would evaluate as 3!. So I used int x = left. I knew that I needed to increase the value of x by multiplying it by a decrementing value starting with x - 1 so I went with y = x - 1. Now each time around, as long as y > 0 remained true, a new value of x would come from the old value of x multiplied by the value of y which reduces by 1 each cycle. I then turn the int result into a double and return the double.

why your functions don't describe a parameter


It's not required. Honestly I don't know. Functions were introduced in ch 4 and here's what it had to say on it.


The list of arguments required by the function is called a parameter list and its elements are called parameters (or formal arguments). The list of parameters can be empty, and if we don’t want to return a result we give void (meaning “nothing”) as the return type. For example:

1
2
3
4
5
 

void write_sorry()
{
      cout << "Sorry\n";
}


The language-technical aspects of functions will be examined more closely in
Chapter 8.

Topic archived. No new replies allowed.