| home
| contents
| previous
| next page
| send comment
| send link
| add bookmark |
Calculator.cpp
/*---------------------------------------------------------------------------------*
* "calculator.cpp"
*
* Definitions for the calculator class. These perform operation on
* spreadsheet data.
*
* Stephen R. Schmitt
*
* January 1999
*/
#include "calculator.h"
#include "scalc.h"
/*---------------------------------------------------------------------------------*
Function description
-------- ----------------------------------------------------------
abs(x) returns the absolute value of x.
acos(x) returns the arccosine of x in the range 0 to pi radians.
If x is less than -1 or greater than 1, acos is indefinite.
asin(x) returns the arcsine of x in the range -pi/2 to pi/2 radians.
If x is less than -1 or greater than 1, asin is indefinite.
atan(x) returns the arctangent of x in the range -pi/2 to pi/2
radians. If x is 0, atan returns 0.
atan2(y,x) returns the arctangent of y/x in the range -pi/2 to pi/2
radians. If both parameters are 0, the function returns 0.
The signs of both parameters are used to determine the
quadrant of the return value.
ceil(x) returns a value representing the smallest integer that is
greater than or equal to x.
cos(x) returns the cosine of angle x. The angle x is assumed to
be in radians.
cosh(x) returns the hyperbolic cosine of angle x. The angle x is
assumed to be in radians.
exp(x) returns the exponential value of x. On overflow,
exp is infinite; on underflow it returns 0.
floor(x) returns a floating-point value representing the largest
integer that is less than or equal to x.
hypot(y,x) returns the length of the hypotenuse of a right triangle,
given the length of the two sides x and y.
ln(x) returns the natural logarithm of x. If x is negative,
it is indefinite. If x is 0, it is infinite.
log(x) returns the base 10 logarithm of x. If x is negative,
it is indefinite. If x is 0, it is infinite.
max(a,b) returns the larger of a and b;
min(a,b) returns the smaller of a and b;
sin(x) returns the sine of x. The angle x is assumed to
be in radians.
sinh(x) returns the hyperbolic sine of x. The angle x is
assumed to be in radians.
sqrt(x) returns the square-root of x. If x is negative, sqrt
is indefinite.
tan(x) returns the tangent of x. The angle x is assumed to
be in radians.
tanh(x) returns the hyperbolic tangent of x. The angle x is
assumed to be in radians.
*---------------------------------------------------------------------*/
FUNCTION flist[] =
{
{ "abs" , ABS },
{ "acos" , ACOS },
{ "asin" , ASIN },
{ "atan" , ATAN },
{ "atan2" , ATAN2 },
{ "ceil" , CEIL },
{ "cos" , COS },
{ "cosh" , COSH },
{ "exp" , EXP },
{ "floor" , FLOOR },
{ "hypot" , HYPOT },
{ "ln" , LN },
{ "log" , LOG },
{ "max" , MAX },
{ "min" , MIN },
{ "sin" , SIN },
{ "sinh" , SINH },
{ "sqrt" , SQRT },
{ "tan" , TAN },
{ "tanh" , TANH },
};
/*---------------------------------------------------------------------------------*
* "evaluate" starts process of cell evaluation including execution of
* any arithmetic operations.
*
* returns: nothing
*/
void calculator::evaluate( int y, // row
int x ) // col
{
bool ok; // success flag
put_cell_status( y, x, EMPTY ); // prevent self reference
get_cell_contents( y, x, cell_contents );
if( !cell_contents[0] )
{
put_cell_status( y, x, EMPTY );
return;
}
Icc = 0; // init contents index
Tos = 0; // init stack index
get_token(); // first token
if( EQUALS == Token.code )
{
get_token(); // after "="
ok = expression();
if( EOLTOK != Token.code ) // should be at end of line
ok = false;
if( ok )
{
// update cell information
put_cell_status( y, x, EXPRESSION );
put_cell_value( y, x, Stack[Tos] );
}
else
{
// indicate syntax error
put_cell_status( y, x, SYNTAX );
put_cell_errloc( y, x, Icc );
}
}
else
put_cell_status( y, x, TEXTCELL );
}
/*---------------------------------------------------------------------------------*
* "recalculate" evaluates every cell in the spreadsheet. This process
* is repeated several times to ensure that all cells reach their
* final values.
*
* returns: nothing
*/
void calculator::recalculate()
{
int x, y, r;
for( r = 0; r < 7; r++ ) // more?
{
for( x = 0; x < CXmax; x++ )
{
for( y = 0; y < CYmax; y++ )
evaluate( y, x );
}
}
}
/*---------------------------------------------------------------------------------*
* "get_token" obtains a token from the cell_contents string. The Token
* data structure is updated.
*
* returns: nothing
*/
void calculator::get_token()
{
char ch; // next char
do // skip whitespace
{
ch = cell_contents[Icc];
Icc++;
}
while( ' ' == ch );
if( isalpha( ch ) ) // function or cell id
get_word( ch );
else if( isdigit( ch ) ) // numbers must begin with digit
get_number( ch );
else // any other punctuation
get_symbol( ch );
}
/*---------------------------------------------------------------------------------*
* "get_word" determines the token corresponding to a word
*
* returns: nothing
*/
void calculator::get_word( char ch ) // first char in word
{
char buffer[MAX_CONTENTS]; // work space
int i = 0; // buffer index
// put seguence of alphanumeric characters into buffer
while( isalnum( ch ) )
{
buffer[i] = char( tolower( ch ) );
i++;
ch = cell_contents[Icc++];
}
// null terminate buffer
Icc--;
buffer[i] = '\0';
// determine token
if( !get_function( buffer ) )
get_cell( buffer );
}
/*---------------------------------------------------------------------------------*
* "get_function" determines the token corresponding to a function.
*
* returns: true if function found
*/
bool calculator::get_function( char *buf ) // function id string
{
int i, end = sizeof( flist ) / sizeof( FUNCTION );
for( i = 0; i < end; i++ )
{
if( !strcmp( buf, flist[i].name ) ) // found match
{
Token.code = flist[i].code;
return true;
}
}
return false;
}
/*---------------------------------------------------------------------------------*
* "get_cell" determines the token corresponding to a cell and determines
* cell location.
*
* note: This function depends on spread sheet having no more than
* nine rows and no more than 26 columns
*
* returns: nothing
*/
void calculator::get_cell( char *buf ) // cell id string
{
int cx, cy;
Token.code = ERRTOK; // default
if( strlen( buf ) != 2 ) // cell id's have two characters
return;
cx = int( buf[0] - 'a' ); // columns lettered A ...
cy = int( buf[1] - '1' ); // rows numbered 1 ...
if( 0 <= cy && cy < CYmax && 0 <= cx && cx < CXmax )
{
Token.cy = cy;
Token.cx = cx;
Token.code = CELL_ID;
}
}
// used in get_number()
const int INTEGER = 0;
const int FRACTION = 1;
const int EXP_SIGN = 2;
const int EXP_DIGIT = 3;
const int EXPONENT = 4;
const int ALL_DONE = 5;
/*---------------------------------------------------------------------------------*
* "get_number" extracts a number token. The first char is always a
* digit.
*
* returns: nothing
*/
void calculator::get_number( char ch ) // first character
{
int j = 0; // buffer index
char number[MAX_CONTENTS]; // buffer number
int state = INTEGER;
Token.code = NUMBER; // assume ok
do
{
number[j++] = ch; // advance
ch = cell_contents[Icc++]; // get next char
switch( state )
{
case INTEGER:
if( 'e' == ch || 'E' == ch )
state = EXP_SIGN;
else if( '.' == ch )
state = FRACTION;
else if( !isdigit( ch ) )
state = ALL_DONE;
break;
case FRACTION:
if( 'e' == ch || 'E' == ch )
state = EXP_SIGN;
else if( !isdigit( ch ) )
state = ALL_DONE;
break;
case EXP_SIGN:
if( '+' == ch || '-' == ch )
state = EXP_DIGIT;
else if( isdigit( ch ) )
state = EXPONENT;
else
{
Token.code = ERRTOK;
state = ALL_DONE;
}
break;
case EXP_DIGIT:
if( isdigit( ch ) )
state = EXPONENT;
else
{
Token.code = ERRTOK;
state = ALL_DONE;
}
break;
case EXPONENT:
if( !isdigit( ch ) )
state = ALL_DONE;
break;
}
}
while( state != ALL_DONE );
Icc--; // backup
number[j] = '\0'; // null terminate
Token.value = atof( number ); // convert to double
}
/*---------------------------------------------------------------------------------*
* "get_symbol" determines the token corresponding to a punctuation
* symbol
*
* returns: nothing
*/
void calculator::get_symbol( char ch ) // the symbol
{
switch( ch )
{
case '\0': Token.code = EOLTOK; break;
case '=': Token.code = EQUALS; break;
case '+': Token.code = ADD; break;
case '-': Token.code = SUBTRACT; break;
case '*': Token.code = MULTIPLY; break;
case '/': Token.code = DIVIDE; break;
case '%': Token.code = FMOD; break;
case '^': Token.code = RAISE; break;
case '(': Token.code = LEFT_PN; break;
case ')': Token.code = RIGHT_PN; break;
case ',': Token.code = COMMA; break;
default: Token.code = ERRTOK; break;
}
}
/*--------------------------------------------------------------------------------*
Expression parsing
Mathematical expressions are evaluated using a recursive descent
algorithm. Cell locations are used as variable identifiers. Expressions
evaluated by SCalc can be described using the Backus-Naur production rules
stated as follows:
<expression> ::= <term> (1.1)
| <sign> <term> (1.2)
| <expression> <additive op> <term> (1.3)
<sign> ::= - | + (2.1)
<additive op> ::= - | + (3.1)
<term> ::= <factor> (4.1)
| <term> <multiplicative op> <factor> (4.2)
<multiplicative op> ::= * | / | % (5.1)
<factor> ::= cell variable (6.1)
| literal number (6.2)
| function call (6.3)
| ( <expression> ) (6.4)
| <atom> (6.5)
<atom> ::= <factor> ^ <factor> (7.1)
Note that rules (1.3) and (4.2) specify that repetition of a sequence of
the same operation are allowed. Rule (6.4) specifies recursion in the
evaluation of sub-expressions.
*---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------------*
* "Expression" parses and executes:
*
* [+,-] <term> { +,- <term> }
*
* returns: false on error
*/
bool calculator::expression()
{
TOKEN op = ADD; // default unary op
// look for a unary operator
if( ADD == Token.code || SUBTRACT == Token.code )
{
op = Token.code;
get_token(); // after unary op
}
if( !term() ) // get first term
return false;
if( SUBTRACT == op )
Stack[Tos] = - Stack[Tos];
while( ADD == Token.code || SUBTRACT == Token.code )
{
op = Token.code; // save operator
get_token(); // after operator
if( !term() ) // get next term(s)
return false;
// perform the operation
if( ADD == op )
Stack[Tos - 1] += Stack[Tos];
else
Stack[Tos - 1] -= Stack[Tos];
Tos--; // pop old stuff
}
return true;
}
/*---------------------------------------------------------------------------------*
* "term" parses and executes:
*
* <factor> { *,/,% <factor> }
*
* returns: false on error
*/
bool calculator::term()
{
TOKEN op; // an operator token
if( !factor() ) // get first factor
return false;
while( MULTIPLY == Token.code ||
DIVIDE == Token.code ||
FMOD == Token.code )
{
op = Token.code; // save operator
get_token(); // after operator
if( !factor() ) // get next factor
return false;
// perform the operation
if( MULTIPLY == op )
Stack[Tos - 1] *= Stack[Tos];
else if( DIVIDE == op )
Stack[Tos - 1] /= Stack[Tos];
else
Stack[Tos - 1] = fmod( Stack[Tos - 1], Stack[Tos] );
Tos--; // pop old stuff
}
return true;
}
/*---------------------------------------------------------------------------------*
* "factor" processes any of:
*
* literal number
* cell variable
* function call
* ( <expression> ) - sub-expression
* <atom> - exponentiation
*
* returns: false on error
*/
bool calculator::factor()
{
bool ok = true;
switch( Token.code )
{
case NUMBER: // literal number
Tos++;
Stack[Tos] = Token.value; // push onto stack
get_token(); // after <number>
break;
case CELL_ID:
if( EXPRESSION == get_cell_status( Token.cy, Token.cx ) )
{
// push result of expression onto stack
Tos++;
Stack[Tos] = get_cell_value( Token.cy, Token.cx );
get_token();
}
else
ok = false; // syntax error
break;
case ABS: case ACOS: case ASIN: case ATAN:
case CEIL: case COS: case COSH: case EXP:
case FLOOR: case LN: case LOG: case SIN:
case SINH: case SQRT: case TAN: case TANH:
ok = call_function( Token.code );
break;
case ATAN2: case HYPOT: case MAX: case MIN:
ok = call_function2( Token.code );
break;
case LEFT_PN:
get_token(); // after "("
if( !expression() ) // recursion
ok = false;
else if( RIGHT_PN == Token.code )
get_token(); // after ")"
else
ok = false; // syntax error
break;
default:
ok = false;
}
// raise term to a power?
if( Token.code == RAISE )
ok = atom();
return ok;
}
/*------------------------------------------------------------------------------*
* "atom" parses an exponentiation:
*
* <term> ^ <term>
*
* returns: false on error
*/
bool calculator::atom()
{
get_token(); // after "^"
if( !factor() )
return false;
// calculate power and pop old stuff
Stack[Tos - 1] = pow( Stack[Tos - 1], Stack[Tos] );
Tos--;
return true;
}
/*---------------------------------------------------------------------------------*
* "call_function" executes a function call of the form:
*
* function_name ( expression )
*
* returns: false on error
*/
bool calculator::call_function( TOKEN fn ) // function code
{
bool ok = false; // assume error
get_token(); // after fn name
if( LEFT_PN == Token.code )
{
get_token(); // after "("
if( expression() )
{
if( RIGHT_PN == Token.code )
{
exc_function( fn );
get_token(); // after ")"
ok = true;
}
}
}
return ok;
}
/*---------------------------------------------------------------------------------*
* "call_function2" executes a function call of the form:
*
* function_name ( expression, expression )
*
* returns: false on error
*/
bool calculator::call_function2( TOKEN fn ) // function code
{
bool ok = false; // assume error
get_token(); // after fn name
if( LEFT_PN != Token.code )
return false;
get_token(); // after "("
if( !expression() ) // push first arg
return false;
if( COMMA != Token.code )
return false;
get_token(); // after ","
if( !expression() ) // push second arg
return false;
if( RIGHT_PN != Token.code )
return false;
get_token(); // after ")"
exc_function( fn );
return true;
}
/*---------------------------------------------------------------------------------*
* "exc_function" executes a standard function.
*
* note: The result is pushed onto the top of the stack.
*
* returns: nothing
*/
void calculator::exc_function( TOKEN fn ) // function code
{
switch( fn )
{
case ABS: Stack[Tos] = fabs( Stack[Tos] ); break;
case ACOS: Stack[Tos] = acos( Stack[Tos] ); break;
case ASIN: Stack[Tos] = asin( Stack[Tos] ); break;
case ATAN: Stack[Tos] = atan( Stack[Tos] ); break;
case CEIL: Stack[Tos] = ceil( Stack[Tos] ); break;
case COS: Stack[Tos] = cos( Stack[Tos] ); break;
case COSH: Stack[Tos] = cosh( Stack[Tos] ); break;
case EXP: Stack[Tos] = exp( Stack[Tos] ); break;
case FLOOR: Stack[Tos] = floor( Stack[Tos] ); break;
case LN: Stack[Tos] = log( Stack[Tos] ); break;
case LOG: Stack[Tos] = log10( Stack[Tos] ); break;
case SIN: Stack[Tos] = sin( Stack[Tos] ); break;
case SINH: Stack[Tos] = sinh( Stack[Tos] ); break;
case SQRT: Stack[Tos] = sqrt( Stack[Tos] ); break;
case TAN: Stack[Tos] = tan( Stack[Tos] ); break;
case TANH: Stack[Tos] = tanh( Stack[Tos] ); break;
case ATAN2:
Stack[Tos-1] = atan2( Stack[Tos-1], Stack[Tos] );
Tos--;
break;
case HYPOT:
Stack[Tos-1] = hypot( Stack[Tos-1], Stack[Tos] );
Tos--;
break;
case MAX:
Stack[Tos-1] = ( Stack[Tos-1] > Stack[Tos] ) ?
Stack[Tos-1] : Stack[Tos];
Tos--;
break;
case MIN:
Stack[Tos-1] = ( Stack[Tos-1] < Stack[Tos] ) ?
Stack[Tos-1] : Stack[Tos];
Tos--;
break;
default:
assert( false ); // DEBUGGING CODE
}
}
| home
| contents
| previous
| next page
| send comment
| send link
| add bookmark |
Copyright © 2004, Stephen R. Schmitt