A tokenizer that can recognize simple mathematical expressions

Introduction

Here is a finite state machine(FSM) that can recognize integers and floating point numbers as well as mathematical expressions including operators: +, -, *, /, ^ and brackets. However, negative sign and mathematics functions such as sine and logarithms cannot be handled by this machine.

Example

3+4, 2-7^2, 3.1416*9^2/14, (2.18+15.7)/2, ...

You may try to input some mathematical expressions below to see the results

Trial Input


Result

(,4,^,2,+,5,^,2,),^,(,1,/,2,),-,3

Amendment (2/5/2023)

There are some defects found in the above FSM which lead to undetected erroneous cases. For example, expressions such as (3+4)52, (3+4).52 and (3+4.2)52 are accepted by the algorithm. However, the source code given below have not solved this issue. The final solution for fixing the problem can be found in later post.

Source Code

<script> // tokenizer that can handle: // 1. decimals // 2. +, -, *, /, ^ // 3. (, ) // eg. 2.27+3.482*2 -> [2.27, +, 3.482, * 2] // eg. ((2.37-4.28)*5+3)^3-4 // -> [(, (, 2.37, -, 4.28, ), *, 5, +, 3, ), ^, 3, -, 4] function tokenizer(pStr) { var mopr = [43,45,42,47,94]; // +, -, *, /, ^ var mState = 'A'; var mch = ''; // key in char var mcc = 0; // ASCII code of key in char var mtoken = ''; var mQ = []; for (var mi=0; mi<pStr.length; mi++) { mch = pStr.charAt(mi) mcc = mch.charCodeAt(0); // FSM if (mState=='A' && mcc==48) { // A: 0 -> C mtoken += mch; mState = 'C'; } else if (mState=='A' && mcc>=49 && mcc<=57) { // A: 1-9 -> B mtoken += mch; mState = 'B'; } else if (mState=='A' && mcc==40) { // A: ( -> A mQ.push(mch); } else if (mState=='B' && mcc>=48 && mcc<=57) { // B: 0-9 -> B mtoken += mch; } else if (mState=='B' && mcc==41) { // B: ) -> B if (mtoken!='') { mQ.push(parseFloat(mtoken)); } mQ.push(mch); mtoken = ''; } else if (mState=='B' && mcc==46) { // B: . -> D mtoken += mch; mState = 'D'; } else if (mState=='B' && mopr.includes(mcc)) { // B: binary operators -> A if (mtoken!='') { mQ.push(parseFloat(mtoken)); } mQ.push(mch); mtoken = ''; mState = 'A'; } else if (mState=='C' && mcc==46) { // C: . -> D mtoken += mch; mState = 'D'; } else if (mState=='C' && mopr.includes(mcc)) { // C: binary operators -> A mQ.push(parseFloat(mtoken)); mQ.push(mch); mtoken = ''; mState = 'A'; } else if (mState=='D' && mcc>=48 && mcc<=57) { // D: 0-9 -> D mtoken += mch; } else if (mState=='D' && mcc==41) { // D: ) -> D if (mtoken!='') { mQ.push(parseFloat(mtoken)); } mQ.push(mch); mtoken = ''; } else if (mState=='D' && mopr.includes(mcc)) { // D: binary operators -> A if (mtoken!='') { mQ.push(parseFloat(mtoken)); } mQ.push(mch); mtoken = ''; mState = 'A'; } else { mState = 'Error'; break; } } // handle the last token if (['B','C','D'].includes(mState)) { if (mtoken!='') { mQ.push(parseFloat(mtoken)); } } else { // invalid token mQ = []; } return mQ; }