Class CCalculator

This is an example of using the FSM library to evaluate simple arithmetic expressions. The example is based on work originally found in a Libero Example. This class defines methods within an FSM to accept an arithmetic expression, parse the expression and calculate the result from expression. The program accepts strings like "8+sqrt(4*4 - 4*8*5) and calculates the result.   

CCalculator combines several basic programming techniques: token parsing, push-down stacks for the operands and operators, and FSM states to indicate what tokens are valid and how valid tokens are handled. The basic idea is to parse the expression into tokens that are either an operand or operator one by one, then stack and evaluate the tokens according to the priority rules until reaching the end of the expression. The tokens are classified as:

• operands: any valid integer or double
• unary operator: +,-,!(not), cos, sin, tan, atan, log, log10
• operator: +,-,*,/,(,),<,>,&,|,<=,>=,==,
• left-parenthesis: '('
• right-parenthesis: ')'
• end-mark: indicates the end of the expression.

Within a given state, it can accept specific tokens and reject others. For instance, at the start of the expression, an operator such as '(', sqrt, or an operand like '8.24' are valid while operators like '*' or ')' are not valid. The primary CCalculator states are EXPECTING-OPERAND,  EXPECTING-OPERATOR,  and  TERMINATE-PROGRAM.    

When in the  EXPECTING-OPERAND state, it will accept an operand token and push its value onto the operand push-down stack. The  EXPECTING-OPERAND state will accept a unaryoperator token (i.e., ' +' or '-' ), and uses a guardian condition to determine the next state in which to transition. The guardian condition uses the lookahead token to detemine if the next token is a number. If the lookahead token is a number, the transition action is to do a  stacksignednumber action and place the number on the operand stack,  otherwise the transition action is logs the FAILED state where it logs an error message. The same condition is used for both transitions and the fail transition uses the "invert" of the guardian function to determine an error condition.

The  EXPECTING-OPERAND state will accept a '(' operator and place it on the operator stack, that will be later matched when unstacking the operators with a ')' operator.  When in the  EXPECTING-OPERATOR state, it will accept an operator token, but before it will stack the operator, it evaluates any previous operators that have the same, or higher priority on the operator, (such as '*' and '/'  higher priority than '+' and '-') and push its value onto the operand push-down stack. When evaluating the top operator and the operand stack are passed to opeEVAL, which pops one or two operands depending on the number required by the operator, does the calculation and pushed the new value onto the operand stack.

A special end-mark token signals the end of the expression and from most states causes a transition to the TERMINATE-PROGRAM state, whereby it evaluates any remaining operators, which leaves the result of the expression on top of the operand stack. Some error checking is performed while parsing and evaluating the expression so that any errors cause the FSM to transition to the FAILED state, enters an error message and then quit. 

The calculate uses the following state logic to parse expressions:

FSM Calculator     First State = EXPECTING-OPERAND

Beginning State	Event	Conditions	Ending State	Actions
EXPECTING-OPERAND	operator	checkSignedNumber	EXPECTING-OPERATOR	stacksignednumber
EXPECTING-OPERAND	operator	NOT(checkSignedNumber)	EXPECTING-OPERATOR	failedSignedNumber
EXPECTING-OPERAND	unaryoperator		EXPECTING-OPERAND	allowunaryoperator
EXPECTING-OPERAND	number		EXPECTING-OPERATOR	stackNumber
EXPECTING-OPERAND	left-paren		EXPECTING-OPERAND	stackLeftParen
EXPECTING-OPERAND	end-mark		TERMINATE-PROGRAM	terminate
EXPECTING-OPERAND	fail		FAILED	fail
EXPECTING-OPERATOR	operator		EXPECTING-OPERAND	unstackGEOperator stackOperator
EXPECTING-OPERATOR	number		FAILED	noOperation
EXPECTING-OPERATOR	right-paren		EXPECTING-OPERATOR	unstackAllOperators unstackIfLeftParen
EXPECTING-OPERATOR	end-mark		TERMINATE-PROGRAM	unstackAllOperators
EXPECTING-OPERATOR	fail		FAILED	fail
TERMINATE-PROGRAM	end-mark		TERMINATE-PROGRAM	terminate
TERMINATE-PROGRAM	fail		FAILED	fail

Examples of the potential calculations that can be performed include:

 
	printf("Calculate -224= %S\n", (BSTR)calc->calculate(L"-224"));
	printf("Calculate -22+4= %S\n", (BSTR)calc->calculate(L"22+4"));
	printf("Calculate 2+2+4= %S\n",(BSTR)calc->calculate(L"2+2+4"));
	printf("Calculate1==1= %S\n", (BSTR)calc->calculate(L"1==1"));
	printf("Calculate0==1= %S\n", (BSTR)calc->calculate(L"0==1"));
	printf("Calculate!(0==1)= %S\n", (BSTR)calc->calculate(L"!(0==1)"));
	printf("Calculate (6-2)5= %S\n", (BSTR)calc->calculate(L"(6-2)5"));
	printf("Calculate sqrt(2+2)+6= %S\n", (BSTR)calc->calculate(L"sqrt(2+2)+6"));

Using the calculator to compute (6 - 2) * 5, we can follow the execution to see how the states changes evolve over time. Nothing fancy is happening, however, note that multiple actions can occur per state transitions.

Current State EXPECTING-OPERAND 
Event = left-paren 
stackLeftParen action 

Current State EXPECTING-OPERAND 
Event = numberToken Value = 6.000000 
stackNumber action 

Current State EXPECTING-OPERATOR 
Event = operator Token Value = - 
unstackGEOperator action 
stackOperator action 

Current State EXPECTING-OPERAND 
Event = numberToken Value = 2.000000 
stackNumber action 

Current State EXPECTING-OPERATOR 
Event =  right-paren 
unstackAllOperators  action 
Evaluate Op - with 2.000000 and  [6.000000] to  give Result 4.000000 

Current State EXPECTING-OPERATOR 
Event = operator Token Value =    
unstackGEOperator action 
stackOperator action 

Current State  EXPECTING-OPERAND 
Event =   number Token Value =    5.000000 
stackNumber  action 

Current  State EXPECTING-OPERATOR 
Event =  end-mark 
unstackAllOperators action 
Evaluate  Op  with 5.000000  and [4.000000] to  give Result 20.000000 

Current State TERMINATE-PROGRAM 
Event =  end-mark 
terminate action 

Calculate  (6-2)5 =   20.000000 

Performance timing and execution statistics are maintained automatically within the FiniteStateMachine. Statistics that are provided include the duration information while in a state: average, worst case and total elapsed, and processing profile while in a state: average, worst case and total. The duration measures the total time in a state, while the processing profile measures the CPU time per state. Every update logs the statistics associated with the updated state and within the overall FiniteStateMachine preformance.  The performance timing provides a simple analysis of the FiniteStateMachine states visited, which  you can use to assess the run-time behavior of your programs. By using execution statistics information, you can determine which states of your code are being used frequently, whether the states have bounded performance, and if they use the CPU efficiently. 

Performance timing, like profiling, is a tuning process, that helps you make your programs run better, but unlike profiling, can help you determine program correctness bugs. Some potential logic problems that may be found include unused states, states that exceed hard-real-time processing constraints, and timing consuming states. 

To  dump the FSM performance timing, the information can be dumped after the FSM has completed by invoking the method timingToHTM and easily saved to file.. 

	String timing=calc->timingToHTML();
	timing.saveFile("FSM Performance Statistics");

The performance timing is given as a table  in HTML format, which can easily be copied and pasted into other word processing formats. Below is an example of the calculator timing (which is so fast the state CPU processing is zero).

FSM Calculator Processing (in seconds)

State	Average Duration	Worst Case Duration	Total Elapsed Duration	Average Processing	Worst Case Processing	Total Processing
EXPECTING-OPERAND	0.030389	0.547000	4.472000	0.000696	0.016000	0.250000
EXPECTING-OPERATOR	0.033118	0.563000	4.738000	0.000800	0.016000	0.313000
FAILED	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000
TERMINATE-PROGRAM	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000

Source

See Also:

Source

Method Detail

CCalculator

~CCalculator

calculate

Calculate is the main function for the class. It accepts an expression, resets the logic, and loops parsing and then transitioning the FSM to handle the token.

Returns:

result as a string. Error message if failed.

checkSignedNumber

Condition to check if valid signed number, when expecting regular number/operand. If current token is of type opPLUS or opMINUS, then determine sign, and do lookahead of next token. If next token type is of number, return true, otherwiswe false. If current token is not of type opPLUS or opMINUS, then return false.

Returns:

true unary operator with number, false otherwise.

fail

Failure of some sort. If Event is of type CFSMFailedEvent then log error message. Otherwise, specify non-specific error. Sets done flag to -1.

Returns:

S_OK error message logged.

failedSignedNumber

Failure of some signed number sort. If current token is not of type opPLUS or opMINUS, then issue internal Fail event Illegal Operator". Else lookahead token was not a number so issue internal Fail event "Expecting number after sign". Sets done flag to -1.

Returns:

S_OK error message logged.

getNextToken

Get the next token from the line. If no token remaining, set end-mark as token. Process token type as event.

Returns:

S_OK always.

noOperation

Dummy nop action.

Returns:

S_OK always.

opEVAL

Evaluates a operation as given by an OPTYPE op, and operands from the operand stack. Pops number of operands depending on operator type, calculates, and pushes the result back on the operand stack.

Returns:

0 ok.

1 couldn't find matching operation based on operator.

resetFSM

Reset calculator FSM and looping logic. Set looping doneFlag to false. CFiniteStateMachine::resetFSM(); Clear operators stack, operands stack, and push opENDMARK onto operators stack.

setupFSM

Setup assigns event, actions, and state transition to all states in the calculator.

stackLeftParen

Stack left parenthesis action.

Returns:

S_OK always.

stackNumber

Stack number action. If current token is of type operator, then push token.optype onto operators stack; else raise internal fail event "Expecting Operator".

Returns:

S_OK always. States handles errors.

stackOperator

Stack operator action. If current token is of type operator, then push token.optype onto operators stack; else raise internal fail event "Expecting Operator".

Returns:

S_OK always. States handles errors.

stacksignednumber

Stack signed number, when expecting regular number/operand. If current token is of type opPLUS or opMINUS, then determine sign, and do lookahead (cheating yes.) by getting next token. If type is of number, push number on operands stack, else issue internal Fail event "Expecting number after sign". If current token is not of type opPLUS or opMINUS, then issue internal Fail event Illegal Operator".

Returns:

S_OK always. States handles errors.

stackunaryoperator

Action to stack unary operator on operator stack. If current token is not unary operator, issue internal Fail event "Expecting Unary Operator".

Returns:

S_OK always. States handles errors.

terminate

Terminate calculation. Should be opENDMARK on the operators stack. If proper ending, sets done flag to -1 so calculation loop ends. Otherwise, the calculation failed, and issue internal failed event.

Returns:

S_OK even when transition to fail state.

unstackAllOperators

Unstack all operators on the operator stack. If operators evaluation is missing operand, raise internal fail event, "Missing Operaand".

Returns:

S_OK always. State transitions handle failures.

unstackGEOperator

Unstack operators that are of greater precedence than the current operator. If the operator on the top is of greater rank than the current token operator, evaluate the top of the operator stack.

unstackIfLeftParen

If top operator is left parenthesis, then unstack and evaluate operators. Has kludge to check for unary operator such as fcn in fcn(x) before ( Obvious kludge as some are fcn(x,y), to be handled later If operators is not opLFPAREN then issue internal fail event because of "Mismatched Parentheses".

Returns:

S_OK even if failed.