Newer
Older
var fsm = function () {
const debugging = false;
const debug = function (msg) {
if (debugging) {
console.log(msg);
}
};
/**
* a fsm that tries to match string "abb". see function
* matchesSubstringAbb.
*/
const matchAbbMachine = function () {
const stateWaitForA = "wait for a";
const stateWaitForFirstB = "wait for 1st b";
const stateWaitForSecondB = "wait for 2nd b";
const stateSucceed = "succeed";
this.currentState = "wait for a";
this.readch = function (ch) {
switch (this.currentState) {
this.currentState = stateWaitForFirstB;
this.currentState = stateWaitForA;
this.currentState = stateWaitForSecondB;
} else if (ch === 'a') {
// do nothing, keep current state.
} else {
this.currentState = stateWaitForA;
this.currentState = stateSucceed;
this.currentState = stateWaitForFirstB;
this.currentState = stateWaitForA;
}
break;
case this.succeed:
// do nothing, keep current state.
break;
}
debug("readch " + ch + ", currentState is " + this.currentState);
return this.currentState;
};
};
/**
* return true if given string has substring "abb" in it.
* implemented using fsm.
*/
const matchesSubstringAbb = function (str) {
const machine = new matchAbbMachine();
for (i = 0; i < str.length; ++i) {
machine.readch(str[i]);
if (machine.currentState === "succeed") {
// console.log("matches");
return true;
}
}
return false;
};
/**
* a fsm that implement a RPN calculator. see document in ./operational
*/
const RPNCalculator = function () {
// states
const stateIdle = "idle";
const stateWaitingForNumberOrAction = "waiting for number or action";
const keyNames = {
num0: "num0",
num1: "num1",
num2: "num2",
num3: "num3",
num4: "num4",
num5: "num5",
num6: "num6",
num7: "num7",
num8: "num8",
num9: "num9",
dot: "dot",
backspace: "backspace",
times: "times",
divide: "divide",
plus: "plus",
minus: "minus",
sum_all: "sum-all",
square_root: "square-root",
power: "power",
swap: "swap",
undo: "undo",
"return": "return",
change_sign: "change-sign",
// map keyName to short key name.
const shortKeyNames = {
"num0": "0",
"num1": "1",
"num2": "2",
"num3": "3",
"num4": "4",
"num5": "5",
"num6": "6",
"num7": "7",
"num8": "8",
"num9": "9",
"dot": ".",
"backspace": "bksp",
"times": "*",
"divide": "/",
"plus": "+",
"minus": "-",
"sum-all": "Σ",
"square-root": "sqrt",
"power": "pow",
"swap": "swap",
"undo": "undo",
"return": "ret",
"change-sign": "chs",
const msgTooFewElementsOnStack = "Too few elements on stack";
const trailHistorySize = 100;
const undoHistorySize = 100;
this.currentState = stateIdle;
this.numberStack = [];
this.currentNumber = "";
this.lastError = null;
/**
* save current state of this FSM. You can use load to restore the FSM state.
*/
this.save = function () {
return {
"currentState": this.currentState,
"currentNumber": this.currentNumber,
};
};
/**
* load saved data back to this FSM. current FSM status will be lost.
*/
this.load = function (data) {
this.currentState = data.currentState;
this.currentNumber = data.currentNumber;
};
/**
* set error msg. only the last error msg can be fetched via this.lastError.
*/
this.setErrorMsg = function (msg) {
console.log(msg);
this.lastError = msg;
};
/**
* clear error msg.
*/
this.clearErrorMsg = function () {
this.lastError = null;
};
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
/**
* do calculator for an unary operator.
* this handles not enough element in stack problem.
*
* it may modify this.numberStack and this.lastError.
*
* Return true on success, return false on failure.
* You may do early return if this function fails. this.lastError will
* be set when false is returned.
*/
this.doUnaryOperator = function (keyName, func) {
this.snapshots.push(this.save());
const num = this.numberStack.pop();
if (num === undefined) {
this.setErrorMsg(msgTooFewElementsOnStack);
this.snapshots.pop();
return false;
}
const result = func(num);
if (result === undefined || result === null || result === false) {
// this does consume the number. Just don't push result
// to number stack.
if (this.lastError === null) {
this.setErrorMsg("result of this operator is undefined or null");
}
return false;
}
this.numberStack.push(result);
this.trail.push([shortKeyName(keyName), result]);
return true;
};
/**
* do calculation for a binary operator.
* this handles not enough element in stack problem.
*
* it may modify this.numberStack and this.lastError.
*
* Return true on success, return false on failure.
* You may do early return if this function fails. this.lastError will
* be set when false is returned.
*/
const num2 = this.numberStack.pop();
if (num2 === undefined) {
this.setErrorMsg(msgTooFewElementsOnStack);
return false;
}
const num1 = this.numberStack.pop();
if (num1 === undefined) {
this.setErrorMsg(msgTooFewElementsOnStack);
this.numberStack.push(num2);
return false;
}
const result = func(num1, num2);
if (result === undefined || result === null || result === false) {
// this does consume the two numbers. Just don't push result
// to number stack.
if (this.lastError === null) {
this.setErrorMsg("result of this operator is undefined or null");
}
return false;
}
this.numberStack.push(result);
/**
* return true if given keyName is one of number keys.
* number keys include num0-9 and dot.
*/
const isNumberKey = function (keyName) {
return (keyNames[keyName] !== undefined) && (keyName.startsWith("num") || keyName === keyNames.dot);
};
/**
* operator key names.
*/
const operatorKeyList = [
keyNames.change_sign,
keyNames.plus, keyNames.minus, keyNames.times, keyNames.divide,
keyNames.swap, keyNames.undo, keyNames.sum_all, keyNames.square_root,
];
const isOperator = function (keyName) {
return operatorKeyList.indexOf(keyName) !== -1;
};
/**
* keys that is not a simple operator.
*/
const miscKeyList = [keyNames["return"], keyNames.undo, keyNames.backspace];
const isMiscKey = function (keyName) {
return miscKeyList.index(keyName) !== -1;
};
/**
* convert number key to a number string.
*/
const numKeyToNumString = function (keyName) {
console.assert(isNumberKey(keyName), "not a number key: " + keyName);
if (keyName === keyNames.dot) {
return ".";
} else {
return keyName.substring(3);
}
};
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
/**
* press keyName when existing number string is oldNumberString.
* return [newNumberString, errMsg]
* errMsg will be null if there is no error.
*/
const changeNumberString = function (keyName, oldNumberString) {
if (oldNumberString === "0" && keyName === keyNames.num0) {
return [oldNumberString, "more 0s are ignored"];
} else if (oldNumberString === "" && keyName === keyNames.dot) {
return ["0.", null];
} else if (keyName === keyNames.dot && oldNumberString.indexOf(".") !== -1) {
// Note: do not use indexOf(keyNames.dot) in if condition,
// because the keyName is dot, not ".".
return [oldNumberString, "more dots are ignored"];
} else {
return [oldNumberString + numKeyToNumString(keyName), null];
}
};
const testChangeNumberString = function () {
var r = changeNumberString(keyNames.dot, "");
console.assert(r[0] === "0.");
console.assert(r[1] === null);
r = changeNumberString(keyNames.num1, "");
console.assert(r[0] === "1");
console.assert(r[1] === null);
r = changeNumberString(keyNames.num1, "2");
console.assert(r[0] === "21");
console.assert(r[1] === null);
r = changeNumberString(keyNames.num0, "0");
console.assert(r[0] === "0");
console.assert(r[1] !== null);
r = changeNumberString(keyNames.num0, "12");
console.assert(r[0] === "120");
console.assert(r[1] === null);
r = changeNumberString(keyNames.dot, "1.2");
console.assert(r[0] === "1.2");
console.assert(r[1] !== null);
};
/**
* return short key name for given keyName.
* this is used to show operator in shorter form in trails.
*/
const shortKeyName = function (keyName) {
return shortKeyNames[keyName];
};
const printSnapshots = function (snapshots) {
debug("printSnapshots()");
const data = snapshots.data;
const l = data.length;
debug("len=" + l);
var i;
for (i = 0; i < l; ++i) {
debug("snapshot[" + i + "]: " + data[i].currentState + ", " + data[i].numberStack);
}
};
const printSnapshot = function (snapshot) {
const msg = "snapshot: " + snapshot.currentState + ", " + snapshot.numberStack;
debug(msg);
return msg;
};
this.sendKey = function (keyName) {
var num, num1, num2;
switch (this.currentState) {
case stateIdle:
if (isNumberKey(keyName)) {
r = changeNumberString(keyName, this.currentNumber);
numString = r[0];
errMsg = r[1];
if (errMsg === null) {
this.currentNumber = numString;
// change state
this.currentState = stateWaitingForNumberOrAction;
// idle state always succeed on number key input.
console.assert(false, "this should not happen");
} else {
switch (keyName) {
case keyNames.round:
if (! this.doUnaryOperator(keyName, (num) => Math.round(num))) {
break;
case keyNames.square_root:
if (! this.doUnaryOperator(keyName, (num) => {
if (num < 0) {
// consumes the number and show error to user.
this.setErrorMsg("square root of negative not supported");
this.snapshots.pop();
return;
}
return Math.pow(num, 0.5);
})) {
return;
}
break;
case keyNames.plus:
if (! this.doBinaryOperator(keyName, (lhs, rhs) => lhs + rhs)) {
case keyNames.minus:
if (! this.doBinaryOperator(keyName, (lhs, rhs) => lhs - rhs)) {
break;
case keyNames.times:
if (! this.doBinaryOperator(keyName, (lhs, rhs) => lhs * rhs)) {
break;
case keyNames.divide:
if (rhs === 0) {
this.setErrorMsg("Division by 0");
return null;
}
return lhs / rhs;
})) {
return;
}
if (! this.doBinaryOperator(keyName, (lhs, rhs) => Math.pow(lhs, rhs))) {
return;
}
break;
num2 = this.numberStack.pop();
if (num2 === undefined) {
this.setErrorMsg(msgTooFewElementsOnStack);
num1 = this.numberStack.pop();
if (num1 === undefined) {
this.setErrorMsg(msgTooFewElementsOnStack);
this.numberStack.push(num2);
this.numberStack.push(num2);
this.numberStack.push(num1);
break;
case keyNames['return']:
// duplicate number
num = this.numberStack.pop();
if (num === undefined) {
this.setErrorMsg(msgTooFewElementsOnStack);
this.numberStack.push(num);
this.numberStack.push(num);
case keyNames.backspace:
// drop one number on stack
num = this.numberStack.pop();
if (num === undefined) {
this.setErrorMsg(msgTooFewElementsOnStack);
return;
}
break;
case keyNames.sum_all:
// sum all numbers of stack
this.snapshots.push(this.save());
r = 0;
num = this.numberStack.pop();
if (num === undefined) {
this.setErrorMsg(msgTooFewElementsOnStack);
this.snapshots.pop();
return;
}
while (num !== undefined) {
r += num;
num = this.numberStack.pop();
}
this.numberStack.push(r);
this.trail.push([shortKeyName(keyName), r]);
break;
case keyNames.undo:
printSnapshots(this.snapshots);
r = this.snapshots.pop();
if (r === undefined) {
this.setErrorMsg("No more undo history!");
return;
} else {
console.log("undo: load saved state: " + printSnapshot(r));
this.load(r);
this.setErrorMsg("Undo!");
// this is a success msg, no need to do early return.
}
break;
default:
console.assert(false, "action not implemented, key is " + keyName);
}
}
break;
case stateWaitingForNumberOrAction:
if (isNumberKey(keyName)) {
r = changeNumberString(keyName, this.currentNumber);
numString = r[0];
errMsg = r[1];
if (errMsg === null) {
this.currentNumber = numString;
} else {
this.setErrorMsg(errMsg);
// keep current state
} else if (keyName === keyNames['return']) {
// commit number to stack
num = parseFloat(this.currentNumber);
this.currentNumber = "";
this.currentState = stateIdle;
r = this.save();
// console.log("save a snapshot: " + r.currentState
// + ", " + r.numberStack + ", " + r.currentNumber);
this.snapshots.push(r);
this.numberStack.push(num);
} else if (keyName === keyNames.backspace) {
if (this.currentNumber.length > 0) {
this.currentNumber = this.currentNumber.substring(0, this.currentNumber.length - 1);
if (this.currentNumber === "") {
this.currentNumber = "0";
}
this.setErrorMsg("no digits to delete");
}
} else if (isOperator(keyName)) {
// commit number
console.log("send return key automatically");
this.sendKey(keyNames['return']);
console.assert(this.currentState === stateIdle,
"auto commit number should set state to idle");
// consume and resend this key. notice the early return.
console.log("resend key " + keyName);
return this.sendKey(keyName);
} else {
switch (keyName) {
default:
console.assert(false, "action not implemented, key is " + keyName);
}
}
break;
default:
console.assert(false, "unknown state: " + this.currentState);
}
debug("sendKey " + keyName + ", currentState is " + this.currentState);
return this.currentState;
};
this.clearTrail = function () {
this.trail.clear();
};
this.clearStack = function () {
this.numberStack = [];
};
this.reset = function () {
this.currentState = stateIdle;
this.numberStack = [];
this.currentNumber = "";
this.lastError = null;
this.trail = new fifo.BoundedQueue(trailHistorySize);
};
const runTests = function () {
testChangeNumberString();
};
matchesSubstringAbb: matchesSubstringAbb,
RPNCalculator: RPNCalculator,