百行代码实现支持括号运算的计算器。相当于一
百行代码实现支持括号运算的计算器。
词法分析将字符序列转换为单词（token）序列的过程。也就是将字符串分割为一个一个的独立小单元。
>> tokenize('11+2+3')
[11, "+", 2, "+", 3]
>> tokenize('333/44+(22+3)')
[333, "/", 44, "+", "(", 22, "+", 3, ")"]
词法分析的实现， 基本思想就是根据字符的属性进行分发处理。
var tokenize = function(s){
var tokens = []
var num = ''
for(var i=0; i<s.length; i++) {
var e = s[i]
if(e === ' ') {
continue
} else if(isSymbol(e)) {
tokens.push(e)
} else if(isNum(e)) {
num += e
if (i+1 === s.length && num != '') { // e为最后一个字符
tokens.push(parseInt(num))
num = ''
}
var next = s[i+1]
if (!isNum(next) && num != '') { // e的下一个字符不为数字字符
tokens.push(parseInt(num))
num = ''
}
} else {
log('error')
break
}
}
return tokens
}
var cutLeft = function(tokens, cutIndex) {
var n = cutIndex
return tokens.slice(0, n)
}
var cutRight = function(tokens, cutIndex) {
return tokens.slice(cutIndex+1, tokens.length)
}
这里将字符分为两类:
var isNum = function(e) {
return '.0123456789'.includes(e)
}
var isSymbol = function(e) {
return e === '(' || e === ')' || e === '+' || e === '-' || e === '*' || e === '/'
}
将token序列转化为方便求值的结构
可以将括号内的token序列作为一个叶子结点，构建一颗树。
>> makeTree([1, "+", "(", 2, "+", 3, ")"])
{
tree: [1, "+", [2, "+", 3]],
count: 7
}
var makeTree = function(tokens) {
var skips = 0
var ret = {
tree: [],
count: 0
}
for(var i=0; i<tokens.length; i++) {
var e = tokens[i]
ret.count ++
if(skips > 0) {
skips --
continue
}
if (e === ')') {
return ret
} else if( e === '(') {
var right = cutRight(tokens, i)
var sub = makeTree(right)
ret.tree.push(sub.tree)
skips = sub.count
} else {
ret.tree.push(e)
}
}
return ret
}
求值
evalExpr函数寻找表达式的运算符， 以运算符为切割点，将表达式分割为左右两个子表达式，对左右子表达式继续进行递归处理。
var evalExpr = function(tokens) {
if(tokens.length == 1) {
var token = tokens[0]
if(isArray(token)) {
return evalExpr(token)
} else {
return token
}
}else{
var sign = ''
var cutIndex = 0
for(var i=0; i<tokens.length; i++) {
token = tokens[i]
if (token == '+' || token == '-') {
sign = token
cutIndex = i
break
}
if (token == '*' || token == '/') {
sign = token
cutIndex = i
continue
}
}
var left = cutLeft(tokens, cutIndex)
var right = cutRight(tokens, cutIndex)
switch(sign) {
case '+':
return evalExpr(left) + evalExpr(right)
case '-':
return evalExpr(left) - evalExpr(right)
case '*':
return evalExpr(left) * evalExpr(right)
case '/':
return evalExpr(left) / evalExpr(right)
}
}
}
var isArray = function(e) {
return Array.isArray(e)
}
版权声明：
1、该文章(资料)来源于互联网公开信息，我方只是对该内容做点评，所分享的下载地址为原作者公开地址。2、网站不提供资料下载，如需下载请到原作者页面进行下载。
