解法主要有两项工作:
1、处理作用域(栈或递归);
2、顺序处理逻辑:(1)根据分隔符将语句拆解为 token;(2)根据关键字的运算逻辑定义状态,设计自动机;(3)从左至右逐个解析 token ,将 token 压入自动机
根据 let、add、mult 三个关键字的逻辑,自动机如下:
JAVA 实现:
public int evaluate(String expression) { Map<String, Stack<Integer>> varMap = new HashMap<String, Stack<Integer>>(); Token token = scope(expression, 0, new Context(ExperStatus.START), varMap); return Integer.valueOf(token.token); } /** * @desc: 处理作用域 * 解析语句有两个任务: * 1、作用域处理(递归处理或栈处理); * 2、自左向右,一个 token 一个 token 的顺序解析语句,处理计算逻辑( token 作为自动机的输入,自动机不断改变状态) */ public Token scope(String expression, int left, Context currentContext, Map<String, Stack<Integer>> varMap) { int len = expression.length(), right = left; // 获取真正的起点指针 if (currentContext.status == ExperStatus.LET) left -= 3; if (currentContext.status == ExperStatus.ADD) left -= 3; if (currentContext.status == ExperStatus.MULT) left -= 4; while (right < len) { char c = expression.charAt(right); if (c == ' ') { right++; continue; } // 一个作用域结束,回归条件 if (c == ')') { System.out.println("running : " + expression.substring(left, right)); if (currentContext.status == ExperStatus.LET) { // 清除作用域中的变量值 Stack<String> varKeyStack = currentContext.varKeyStack; while (varKeyStack != null && varKeyStack.size() > 0) { String key = varKeyStack.pop(); varMap.get(key).pop(); } return new Token(String.valueOf(currentContext.val), left, right + 1); } if (currentContext.status == ExperStatus.ADD2) { return new Token(String.valueOf(currentContext.param1 + currentContext.param2), left, right + 1); } if (currentContext.status == ExperStatus.MULT2) { return new Token(String.valueOf(currentContext.param1 * currentContext.param2), left, right + 1); } } // 解析出一个 token Token currentToken = null; // 新的作用域,整体作为一个 token,递归解析 if (c == '(') { right++; currentToken = getStringToken(expression, right); String keyword = currentToken.token; if ("let".equals(keyword)) currentToken = scope(expression, right + 3, new Context(ExperStatus.LET), varMap); else if ("add".equals(keyword)) currentToken = scope(expression, right + 3, new Context(ExperStatus.ADD), varMap); else if ("mult".equals(keyword)) currentToken = scope(expression, right + 4, new Context(ExperStatus.MULT), varMap); } // 普通的 token else currentToken = getStringToken(expression, right); // token 处理 if (currentContext.status == ExperStatus.ADD) { currentContext.param1 = getParam(currentToken.token, varMap); currentContext.status = ExperStatus.ADD1; } else if (currentContext.status == ExperStatus.MULT) { currentContext.param1 = getParam(currentToken.token, varMap); currentContext.status = ExperStatus.MULT1; } else if (currentContext.status == ExperStatus.ADD1) { currentContext.param2 = getParam(currentToken.token, varMap); currentContext.status = ExperStatus.ADD2; } else if (currentContext.status == ExperStatus.MULT1) { currentContext.param2 = getParam(currentToken.token, varMap); currentContext.status = ExperStatus.MULT2; } else if (currentContext.status == ExperStatus.LET) { if (')' == expression.charAt(currentToken.right)) { currentContext.val = getParam(currentToken.token, varMap); } else { if (null == currentContext.varKeyStack) currentContext.varKeyStack = new Stack<String>(); currentContext.varKeyStack.push(currentToken.token); currentContext.status = ExperStatus.LET1; } } else if (currentContext.status == ExperStatus.LET1) { if (null == currentContext.varValStack) currentContext.varValStack = new Stack<Integer>(); currentContext.varValStack.push(getParam(currentToken.token, varMap)); String key = currentContext.varKeyStack.peek(); int val = currentContext.varValStack.peek(); if (!varMap.keySet().contains(key)) varMap.put(key, new Stack<Integer>()); varMap.get(key).push(val); currentContext.status = ExperStatus.LET; } else if (currentContext.status == ExperStatus.START) { return currentToken; } // 解析完一个 token,指针右移 right = currentToken.right; } return null; } /** * @desc: 解析出一个token */ public Token getStringToken(String expression, int left) { StringBuilder sb = new StringBuilder(); int len = expression.length(), right = left; char c = expression.charAt(right); while (right < len && c != ' ' && c != '(' && c != ')') { sb.append(c); right++; c = expression.charAt(right); } return new Token(sb.toString(), left, right); } public int getParam(String token, Map<String, Stack<Integer>> varMap) { if (null == token || token.length() == 0) throw new NullPointerException(" token is null ! "); char c = token.charAt(0); if (c == '-' || (c >= '0' && c <= '9')) return Integer.valueOf(token); return varMap.get(token).peek(); } /** * @desc: 标识一个 token */ class Token { int left, right; String token; Token(String token, int left, int right) { this.token = token; this.left = left; this.right = right; } } /** * @desc: 当前作用域上下文 */ class Context { ExperStatus status; Stack<String> varKeyStack; Stack<Integer> varValStack; Integer val, param1, param2; Context(ExperStatus status) { this.status = status; } } enum ExperStatus { START, WAIT, LET, LET1, LET2, ADD, ADD1, ADD2, MULT, MULT1, MULT2, COMPLETE }
JS 实现:
/** * @param {string} expression * @return {number} */ var evaluate = function (expression) { return scope(expression, {status: "START"}, 0, new Map()).val; }; var scope = function (expression, currentContext, left, varMap) { let len = expression.length, right = left; if (currentContext.status == "LET") left -= 3; else if (currentContext.status == "ADD") left -= 3; else if (currentContext.status == "MULT") left -= 4; while (right < len) { let c = expression.charAt(right); if (c == ' ') { right++; continue; } if (c == ")") { console.log(expression.substring(left, right)); let resToken = { left: left, right: right + 1 } if (currentContext.status == "LET" || currentContext.status == "LET1") { let varKeyStack = currentContext.varKeyStack; while (varKeyStack && varKeyStack.length > 0) { let key = varKeyStack.pop(); varMap.get(key).pop(); } resToken.val = currentContext.val; } else if (currentContext.status == "ADD2") resToken.val = Number(currentContext.param1) + Number(currentContext.param2); else if (currentContext.status == "MULT2") resToken.val = Number(currentContext.param1) * Number(currentContext.param2); return resToken; } let token; if (c == "(") { let keywordToken = getToken(expression, right + 1); right = keywordToken.right; if ("let" == keywordToken.val) token = scope(expression, {status: "LET"}, right, varMap); else if ("add" == keywordToken.val) token = scope(expression, {status: "ADD"}, right, varMap); else if ("mult" == keywordToken.val) token = scope(expression, {status: "MULT"}, right, varMap); } else token = getToken(expression, right); if (currentContext.status == "LET") { if (expression.charAt(token.right) == ")") currentContext.val = getParam(token.val, varMap); else { if (!currentContext.varKeyStack) currentContext.varKeyStack = []; currentContext.varKeyStack.push(token.val); currentContext.status = "LET1"; } } else if (currentContext.status == "LET1") { if (expression.charAt(token.right) == ")") currentContext.val = getParam(token.val, varMap); else { let key = currentContext.varKeyStack[currentContext.varKeyStack.length - 1], val = getParam(token.val, varMap); if (!currentContext.varValStack) currentContext.varValStack = []; currentContext.varValStack.push(val); if (!varMap.get(key)) varMap.set(key, []); varMap.get(key).push(val); currentContext.status = "LET"; } } else if (currentContext.status == "ADD") { currentContext.param1 = getParam(token.val, varMap); currentContext.status = "ADD1"; } else if (currentContext.status == "ADD1") { currentContext.param2 = getParam(token.val, varMap); currentContext.status = "ADD2"; } else if (currentContext.status == "MULT") { currentContext.param1 = getParam(token.val, varMap); currentContext.status = "MULT1"; } else if (currentContext.status == "MULT1") { currentContext.param2 = getParam(token.val, varMap); currentContext.status = "MULT2"; } else if (currentContext.status == "START") return {val: token.val}; right = token.right; } } var getToken = function (expression, left) { let c = expression.charAt(left), right = left, reStr = ""; while (right < expression.length && c != " " && c != "(" && c != ")") { reStr = reStr + c; right++; c = expression.charAt(right); } console.log(reStr); return { val: reStr, left: left, right: right }; } var getParam = function (token, map) { let exp = /^[+-]?\d*(\.\d*)?(e[+-]?\d+)?$/; if (exp.test(token)) return token; let stack = map.get(token); return stack[stack.length - 1]; }
标签:status,right,Lisp,expression,currentContext,语法,token,varMap,Leetcode736 From: https://www.cnblogs.com/niuyourou/p/17125192.html