Calculator类题目的高级通用解法

magicsets

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由 magicsets 于 2018-1-12 04:14 编辑

这个方法是之前写在另一个帖子里的，觉得有点通用价值所以单独发一下

考虑Calculator的各种题目，例如：
http://www.1point3acres.com/bbs/thread-218681-1-1.html
http://www.1point3acres.com/bbs/thread-266657-1-1.html
http://www.1point3acres.com/bbs/thread-297291-1-1.html
http://www.1point3acres.com/bbs/thread-304410-1-1.html

其实主要区别就是使用的运算符（operator）不同，而一个运算符可以由以下性质所描述：
(1) 词法，也就符号本身
例如 '+'，'-'，'*'，'\'

(2) 元数（arity）
大部分操作符都是二元的，例如加减乘除，也有题目中需要支持一元的取负（'-'）运算符

(3) 优先级（precedence）
一般用一个整数表示

(4) 结合性（associativity）
例如加减乘除都是左结合的，也就是同优先级下，按从左往右的顺序计算；负号则是右结合；也有左右都不结合的运算

结合性有一些表示法，参考这里：http://www.swi-prolog.org/pldoc/man?predicate=op/3

(5) 语义（semantics）
运算符的语义可以表示为宿主语言下的一个函数，例如在Java下，加法的语义就是(a, b) -> a + b

在此基础上，我们可以只写一份基础设施代码，然后对于任意一道变形题目，只需要额外的几行代码描述其中运算符的以上几点性质，就可以自动生成对应功能的Calculator

参考代码如下：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
// 一个使用样例
Calculator calc = new Calculator();
// 中间的数字是优先级（precedence），数字越小优先级越高
// 这里限定二元运算符是left associative，一元运算符是right associative
calc.registerOperation("+", 500, (a, b) -> a + b);
calc.registerOperation("-", 500, (a, b) -> a - b);
calc.registerOperation("*", 400, (a, b) -> a * b);
calc.registerOperation("/", 400, (a, b) -> a / b);
calc.registerOperation("^", 200, (a, b) -> (int) Math.pow(a, b));
calc.registerOperation("-", 100, (a) -> -a);
// 某道Calculator变形题，重定义了"&"和"|"的语义
calc.registerOperation("&", 600, (a, b) -> Math.max(a, b));
calc.registerOperation("|", 800, (a, b) -> Math.min(a, b));
// 也可以支持函数，函数本质上是前缀表达式，就不需要优先级信息了
calc.registerFunction("abs", (int ...a) -> Math.abs(a[0]));
calc.registerFunction("min", (int ...a) -> Arrays.stream(a).min().getAsInt());
calc.registerFunction("max", (int ...a) -> Arrays.stream(a).max().getAsInt());
System.out.println(calc.evaluate("1 + 2 * 3 ^ abs(6 - 3 * 3) + (-8) / (-2)"));
System.out.println(calc.evaluate("min(-3 * 2, -4, -5) * max(5, 6, 7, min(8, 9))"));
}
}
/******************************************************************************
样例：使用下面的Solution类可以通过LeetCode 224
class Solution {
private static Calculator calc = new Calculator();
static {
calc.registerOperation("+", 500, (a, b) -> a + b);
calc.registerOperation("-", 500, (a, b) -> a - b);
calc.registerOperation("-", 100, (a) -> -a);
}
public int calculate(String s) {
return calc.evaluate(s);
}
}
******************************************************************************/
/******************************************************************************
样例：使用下面的Solution类可以通过LeetCode 227
class Solution {
private static Calculator calc = new Calculator();
static {
calc.registerOperation("+", 500, (a, b) -> a + b);
calc.registerOperation("-", 500, (a, b) -> a - b);
calc.registerOperation("*", 400, (a, b) -> a * b);
calc.registerOperation("/", 400, (a, b) -> a / b);
calc.registerOperation("-", 100, (a) -> -a);
}
public int calculate(String s) {
return calc.evaluate(s);
}
}
******************************************************************************/
class Calculator {
private Map<String, OperationInfo<UnaryOperation>> unaryOperations;
private Map<String, OperationInfo<BinaryOperation>> binaryOperations;
private Map<String, Function> functions;
public Calculator() {
this.unaryOperations =
new HashMap<String, OperationInfo<UnaryOperation>>();
this.binaryOperations =
new HashMap<String, OperationInfo<BinaryOperation>>();
this.functions = new HashMap<String, Function>();
}
// 注册一个一元运算符
public void registerOperation(String operator, int precedence,
UnaryOperation operation) {
unaryOperations.put(
operator, new OperationInfo<UnaryOperation>(precedence, operation));
}
// 注册一个二元运算符
public void registerOperation(String operator, int precedence,
BinaryOperation operation) {
binaryOperations.put(
operator, new OperationInfo<BinaryOperation>(precedence, operation));
}
// 注册一个函数
public void registerFunction(String name, Function function) {
functions.put(name, function);
}
// 调用Executor对表达式进行计算
public int evaluate(String expression) {
CalculatorExecutor executor =
new CalculatorExecutor(unaryOperations, binaryOperations,
functions, expression);
return executor.run();
}
}
// 对一元运算符的抽象
interface UnaryOperation {
public int apply(int operand);
}
// 对二元运算符的抽象
interface BinaryOperation {
public int apply(int lhs, int rhs);
}
// 对函数的抽象
interface Function {
public int apply(int ...operands);
}
// 用于打包operation和对应的precedence信息的小类
class OperationInfo<T> {
public final int precedence;
public final T operation;
public OperationInfo(int precedence, T operation) {
this.precedence = precedence;
this.operation = operation;
}
}
// LL(1) Recursive Descent Syntax Directed Translator
class CalculatorExecutor {
private final Map<String, OperationInfo<UnaryOperation>> unaryOperations;
private final Map<String, OperationInfo<BinaryOperation>> binaryOperations;
private final Map<String, Function> functions;
private final String stream;
private int position;
// 词法部分也合并到这个类里了
private enum TokenType {
INTEGER,
NAME,
OPERATOR,
LPAREN,
RPAREN,
COMMA,
EOS,
ERROR
}
private class Token {
public final TokenType type;
public final Object payload;
public final int columnNumber;
public Token(TokenType type, int columnNumber) {
this(type, columnNumber, null);
}
public Token(TokenType type, int columnNumber, Object payload) {
this.type = type;
this.payload = payload;
this.columnNumber = columnNumber;
}
}
private Stack<Token> tokens;
public CalculatorExecutor(
Map<String, OperationInfo<UnaryOperation>> unaryOperations,
Map<String, OperationInfo<BinaryOperation>> binaryOperations,
Map<String, Function> functions,
String stream) {
this.unaryOperations = unaryOperations;
this.binaryOperations = binaryOperations;
this.functions = functions;
this.stream = stream;
this.position = 0;
this.tokens = new Stack<Token>();
}
public int run() {
int value = evalExpr(Integer.MAX_VALUE);
passNextToken(TokenType.EOS);
return value;
}
//////////////////////////////////////////////////////////////////////////////
// 语法处理部分
private int evalExpr(int precedence) {
int value = evalFactor(precedence);
// 二元运算符，注意这里对优先级的处理方法
while (hasNextToken(TokenType.OPERATOR)) {
Token token = nextToken();
OperationInfo<BinaryOperation> info =
binaryOperations.get((String)token.payload);
if (info == null || info.precedence >= precedence) {
pushBack(token);
break;
}
value = info.operation.apply(value, evalExpr(info.precedence));
}
return value;
}
private int evalFactor(int precedence) {
Token token = nextToken();
// Case 1. 数字自身
if (token.type == TokenType.INTEGER) {
return (Integer)token.payload;
}
// Case 2. 一元运算符
if (token.type == TokenType.OPERATOR) {
OperationInfo<UnaryOperation> info =
unaryOperations.get((String)token.payload);
if (info == null || info.precedence > precedence) {
error(token);
}
return info.operation.apply(evalExpr(info.precedence));
}
// Case 3. 函数调用
if (token.type == TokenType.NAME) {
Function func = functions.get((String)token.payload);
if (func == null) {
error(token);
}
ArrayList<Integer> args = new ArrayList<Integer>();
passNextToken(TokenType.LPAREN);
while (!hasNextToken(TokenType.RPAREN)) {
args.add(evalExpr(Integer.MAX_VALUE));
if (!hasNextToken(TokenType.COMMA)) {
break;
}
nextToken();
}
passNextToken(TokenType.RPAREN);
return func.apply(args.stream().mapToInt(x -> x).toArray());
}
// Case 4. 括号表达式
if (token.type == TokenType.LPAREN) {
int value = evalExpr(Integer.MAX_VALUE);
Token rp = nextToken();
if (rp.type != TokenType.RPAREN) {
error(token);
}
return value;
}
error(token);
return 0;
}
//////////////////////////////////////////////////////////////////////////////
// 词法处理部分
private boolean hasNextToken(TokenType ...expected) {
Token token = nextToken();
boolean status = Arrays.stream(expected).anyMatch(x -> x == token.type);
pushBack(token);
return status;
}
private void passNextToken(TokenType ...expected) {
Token token = nextToken();
if (!Arrays.stream(expected).anyMatch(x -> x == token.type)) {
error(token);
}
}
private void pushBack(Token token) {
tokens.add(token);
}
private Token nextToken() {
if (!tokens.isEmpty()) {
return tokens.pop();
}
while (position < stream.length() &&
Character.isWhitespace(stream.charAt(position))) {
++position;
}
if (position >= stream.length()) {
return new Token(TokenType.EOS, position);
}
final int start = position;
final char ch = stream.charAt(position++);
switch (ch) {
case '(': return new Token(TokenType.LPAREN, start);
case ')': return new Token(TokenType.RPAREN, start);
case ',': return new Token(TokenType.COMMA, start);
default: --position; break;
}
if (Character.isDigit(ch)) {
return nextNumber();
}
if (Character.isAlphabetic(ch)) {
return nextName();
}
return nextOperator();
}
private Token nextNumber() {
final int start = position;
while (position < stream.length() &&
Character.isDigit(stream.charAt(position))) {
++position;
}
return new Token(TokenType.INTEGER, start,
Integer.parseInt(stream.substring(start, position)));
}
private Token nextName() {
final int start = position;
while (position < stream.length() &&
Character.isAlphabetic(stream.charAt(position))) {
++position;
}
return new Token(TokenType.NAME, start,
stream.substring(start, position));
}
private Token nextOperator() {
final int start = position;
while (position < stream.length()) {
final char ch = stream.charAt(position);
if (Character.isWhitespace(ch) ||
Character.isDigit(ch) ||
Character.isAlphabetic(ch) ||
ch == '(' || ch == ')' || ch == ',') {
break;
}
++position;
}
return new Token(TokenType.OPERATOR, start,
stream.substring(start, position));
}
private void error(Token token) {
throw new RuntimeException(
"Syntax error: unexpected token at column " +
(token.columnNumber+1) + " -- " + token.type.name() +
(token.payload == null ? "" : " (" + token.payload.toString() + ")"));
}
}

复制代码

biomedicineman

magicsets 发表于 2018-1-12 14:04
谢谢大米

你总结的这么多这么好，应该给你大米的。我再给你点！

magicsets

本帖最后由 magicsets 于 2018-1-13 02:31 编辑

biomedicineman 发表于 2018-1-12 15:00
是啊是啊。最后那种情况压根就不是计算器了。。。所以我最后这个面试的时候没做出来。。。至今也没时间fi ...

我把这个也写了下，但是代码量多了不少... 主要是110行到294行的语法树的处理方面，供参考~ （PS 感谢你的大米！不用再加了哈）

（不过目前这个代码不考虑运算符的交换性、结合性和分配性 -- 比如(1 + x - 2) * 3可以化简为x*3 - 3 -- 要支持这些的话要写一个rule-based system对语法树进行各种变换）

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
import java.util.StringJoiner;
public class Main {
public static void main(String[] args) {
// 一个使用样例
Calculator calc = new Calculator();
// 中间的数字是优先级（precedence），数字越小优先级越高
// 这里限定二元运算符是left associative，一元运算符是right associative
calc.registerOperation("+", 500, (a, b) -> a + b);
calc.registerOperation("-", 500, (a, b) -> a - b);
calc.registerOperation("*", 400, (a, b) -> a * b);
calc.registerOperation("/", 400, (a, b) -> a / b);
calc.registerOperation("^", 200, (a, b) -> (int) Math.pow(a, b));
calc.registerOperation("-", 100, (a) -> -a);
// 也可以支持函数，函数本质上是前缀表达式，就不需要优先级信息了
calc.registerFunction("abs", (int ...a) -> Math.abs(a[0]));
calc.registerFunction("min", (int ...a) -> Arrays.stream(a).min().getAsInt());
calc.registerFunction("max", (int ...a) -> Arrays.stream(a).max().getAsInt());
calc.setVariable("software", 3);
String s1 = calc.evaluate("software * 2 + (1 - hardware) * (2 + 3) + min(a + 5, 3 * 8)");
System.out.println("s1 = " + s1);
// 输出：s1 = 6 + (1 - hardware) * 5 + min(a + 5, 24)
calc.setVariable("hardware", 5);
String s2 = calc.evaluate(s1);
System.out.println("s2 = " + s2);
// 输出：s2 = -14 + min(a + 5, 24)
calc.setVariable("a", 10);
String s3 = calc.evaluate(s2);
System.out.println("s3 = " + s3);
// 输出：s3 = 1
}
}
class Calculator {
private Map<String, OperationInfo<UnaryOperation>> unaryOperations;
private Map<String, OperationInfo<BinaryOperation>> binaryOperations;
private Map<String, Function> functions;
private Map<String, Integer> environment;
public Calculator() {
this.unaryOperations =
new HashMap<String, OperationInfo<UnaryOperation>>();
this.binaryOperations =
new HashMap<String, OperationInfo<BinaryOperation>>();
this.functions = new HashMap<String, Function>();
this.environment = new HashMap<String, Integer>();
}
// 注册一个一元运算符
public void registerOperation(String operator, int precedence,
UnaryOperation operation) {
unaryOperations.put(
operator, new OperationInfo<UnaryOperation>(precedence, operation));
}
// 注册一个二元运算符
public void registerOperation(String operator, int precedence,
BinaryOperation operation) {
binaryOperations.put(
operator, new OperationInfo<BinaryOperation>(precedence, operation));
}
// 注册一个函数
public void registerFunction(String name, Function function) {
functions.put(name, function);
}
// 设置变量的值
public void setVariable(String name, int value) {
environment.put(name, value);
}
// 调用Executor对表达式进行计算
public String evaluate(String expression) {
CalculatorExecutor executor =
new CalculatorExecutor(unaryOperations, binaryOperations,
functions, environment, expression);
return executor.run().toString();
}
}
// 对一元运算符的抽象
interface UnaryOperation {
public int apply(int operand);
}
// 对二元运算符的抽象
interface BinaryOperation {
public int apply(int lhs, int rhs);
}
// 对函数的抽象
interface Function {
public int apply(int ...operands);
}
// 语法树
abstract class Expression {
public abstract int getPrecedence();
public abstract String toString();
public abstract Expression eval(Map<String, Integer> environment);
protected String addParenthese(String s, int innerPrecedence) {
return innerPrecedence >= getPrecedence() ? "(" + s + ")" : s;
}
}
// 语法树：一元表达式
class UnaryExpression extends Expression {
private final String operator;
private final UnaryOperation operation;
private final int precedence;
private final Expression operand;
public UnaryExpression(String operator, UnaryOperation operation,
int precedence, Expression operand) {
this.operator = operator;
this.operation = operation;
this.precedence = precedence;
this.operand = operand;
}
@Override
public Expression eval(Map<String, Integer> environment) {
Expression result = operand.eval(environment);
if (result instanceof Literal) {
return new Literal(operation.apply(((Literal)result).value));
}
return new UnaryExpression(operator, operation, precedence, result);
}
@Override
public int getPrecedence() {
return precedence;
}
@Override
public String toString() {
return operator + addParenthese(operand.toString(), operand.getPrecedence());
}
}
// 语法树：二元表达式
class BinaryExpression extends Expression {
private final String operator;
private final BinaryOperation operation;
private final int precedence;
private final Expression lhsOperand;
private final Expression rhsOperand;
public BinaryExpression(String operator,
BinaryOperation operation, int precedence,
Expression lhsOperand, Expression rhsOperand) {
this.operator = operator;
this.operation = operation;
this.precedence = precedence;
this.lhsOperand = lhsOperand;
this.rhsOperand = rhsOperand;
}
@Override
public Expression eval(Map<String, Integer> environment) {
Expression lhsResult = lhsOperand.eval(environment);
Expression rhsResult = rhsOperand.eval(environment);
if (lhsResult instanceof Literal && rhsResult instanceof Literal) {
return new Literal(
operation.apply(((Literal)lhsResult).value, ((Literal)rhsResult).value));
}
return new BinaryExpression(operator, operation, precedence, lhsResult, rhsResult);
}
@Override
public int getPrecedence() {
return precedence;
}
@Override
public String toString() {
return addParenthese(lhsOperand.toString(), lhsOperand.getPrecedence() - 1) +
" " + operator + " " +
addParenthese(rhsOperand.toString(), rhsOperand.getPrecedence());
}
}
// 语法树：函数调用
class FunctionCall extends Expression {
private final String functor;
private final Function function;
private final Expression[] arguments;
public FunctionCall(String functor,
Function function,
Expression[] arguments) {
this.functor = functor;
this.function = function;
this.arguments = arguments;
}
@Override
public Expression eval(Map<String, Integer> environment) {
Expression[] results = new Expression[arguments.length];
for (int i = 0; i < arguments.length; ++i) {
results[i] = arguments[i].eval(environment);
}
boolean allLiterals =
Arrays.stream(results).allMatch(arg -> arg instanceof Literal);
if (allLiterals) {
int[] literals = new int[arguments.length];
for (int i = 0; i < arguments.length; ++i) {
literals[i] = ((Literal)results[i]).value;
}
return new Literal(function.apply(literals));
}
return new FunctionCall(functor, function, results);
}
@Override
public int getPrecedence() {
return 0;
}
@Override
public String toString() {
StringJoiner argJoiner = new StringJoiner(", ");
for (Expression arg : arguments) {
argJoiner.add(arg.toString());
}
return functor + "(" + argJoiner.toString() + ")";
}
}
// 语法树：常量值
class Literal extends Expression {
public final int value;
public Literal(int value) {
this.value = value;
}
@Override
public Expression eval(Map<String, Integer> environment) {
return this;
}
@Override
public int getPrecedence() {
return 0;
}
@Override
public String toString() {
return String.valueOf(value);
}
}
// 语法树：变量
class Variable extends Expression {
private final String name;
public Variable(String name) {
this.name = name;
}
@Override
public Expression eval(Map<String, Integer> environment) {
Integer value = environment.get(name);
return value == null ? this : new Literal(value);
}
@Override
public int getPrecedence() {
return 0;
}
@Override
public String toString() {
return name;
}
}
// 用于打包operation和对应的precedence信息的小类
class OperationInfo<T> {
public final int precedence;
public final T operation;
public OperationInfo(int precedence, T operation) {
this.precedence = precedence;
this.operation = operation;
}
}
// LL(1) Recursive Descent Syntax Directed Translator
class CalculatorExecutor {
private final Map<String, OperationInfo<UnaryOperation>> unaryOperations;
private final Map<String, OperationInfo<BinaryOperation>> binaryOperations;
private final Map<String, Function> functions;
private Map<String, Integer> environment;
private final String stream;
private int position;
// 词法部分也合并到这个类里了
private enum TokenType {
INTEGER,
NAME,
OPERATOR,
LPAREN,
RPAREN,
COMMA,
EOS,
ERROR
}
private class Token {
public final TokenType type;
public final Object payload;
public final int columnNumber;
public Token(TokenType type, int columnNumber) {
this(type, columnNumber, null);
}
public Token(TokenType type, int columnNumber, Object payload) {
this.type = type;
this.payload = payload;
this.columnNumber = columnNumber;
}
}
private Stack<Token> tokens;
public CalculatorExecutor(
Map<String, OperationInfo<UnaryOperation>> unaryOperations,
Map<String, OperationInfo<BinaryOperation>> binaryOperations,
Map<String, Function> functions,
Map<String, Integer> environment,
String stream) {
this.unaryOperations = unaryOperations;
this.binaryOperations = binaryOperations;
this.functions = functions;
this.environment = environment;
this.stream = stream;
this.position = 0;
this.tokens = new Stack<Token>();
}
public Expression run() {
Expression expr = parseExpr(Integer.MAX_VALUE);
passNextToken(TokenType.EOS);
return expr.eval(environment);
}
//////////////////////////////////////////////////////////////////////////////
// 语法处理部分
private Expression parseExpr(int precedence) {
Expression expr = parseFactor(precedence);
// 二元运算符，注意这里对优先级的处理方法
while (hasNextToken(TokenType.OPERATOR)) {
Token token = nextToken();
String operator = (String)token.payload;
OperationInfo<BinaryOperation> info = binaryOperations.get(operator);
if (info == null || info.precedence >= precedence) {
pushBack(token);
break;
}
expr = new BinaryExpression(operator, info.operation, info.precedence,
expr, parseExpr(info.precedence));
}
return expr;
}
private Expression parseFactor(int precedence) {
Token token = nextToken();
// Case 1. 数字自身
if (token.type == TokenType.INTEGER) {
return new Literal((Integer)token.payload);
}
// Case 2. 一元运算符
if (token.type == TokenType.OPERATOR) {
String operator = (String)token.payload;
OperationInfo<UnaryOperation> info = unaryOperations.get(operator);
if (info == null || info.precedence > precedence) {
error(token);
}
return new UnaryExpression(operator, info.operation,
info.precedence, parseExpr(info.precedence));
}
// Case 3. 函数调用或者变量
if (token.type == TokenType.NAME) {
if (hasNextToken(TokenType.LPAREN)) {
String functor = (String)token.payload;
Function function = functions.get(functor);
if (function == null) {
error(token);
}
ArrayList<Expression> args = new ArrayList<Expression>();
passNextToken(TokenType.LPAREN);
while (!hasNextToken(TokenType.RPAREN)) {
args.add(parseExpr(Integer.MAX_VALUE));
if (!hasNextToken(TokenType.COMMA)) {
break;
}
nextToken();
}
passNextToken(TokenType.RPAREN);
return new FunctionCall(
functor, function, args.toArray(new Expression[args.size()]));
} else {
return new Variable((String)token.payload);
}
}
// Case 4. 括号表达式
if (token.type == TokenType.LPAREN) {
Expression expr = parseExpr(Integer.MAX_VALUE);
Token rp = nextToken();
if (rp.type != TokenType.RPAREN) {
error(token);
}
return expr;
}
error(token);
return null;
}
//////////////////////////////////////////////////////////////////////////////
// 词法处理部分
private boolean hasNextToken(TokenType ...expected) {
Token token = nextToken();
boolean status = Arrays.stream(expected).anyMatch(x -> x == token.type);
pushBack(token);
return status;
}
private void passNextToken(TokenType ...expected) {
Token token = nextToken();
if (!Arrays.stream(expected).anyMatch(x -> x == token.type)) {
error(token);
}
}
private void pushBack(Token token) {
tokens.add(token);
}
private Token nextToken() {
if (!tokens.isEmpty()) {
return tokens.pop();
}
while (position < stream.length() &&
Character.isWhitespace(stream.charAt(position))) {
++position;
}
if (position >= stream.length()) {
return new Token(TokenType.EOS, position);
}
final int start = position;
final char ch = stream.charAt(position++);
switch (ch) {
case '(': return new Token(TokenType.LPAREN, start);
case ')': return new Token(TokenType.RPAREN, start);
case ',': return new Token(TokenType.COMMA, start);
default: --position; break;
}
if (Character.isDigit(ch)) {
return nextNumber();
}
if (Character.isAlphabetic(ch)) {
return nextName();
}
return nextOperator();
}
private Token nextNumber() {
final int start = position;
while (position < stream.length() &&
Character.isDigit(stream.charAt(position))) {
++position;
}
return new Token(TokenType.INTEGER, start,
Integer.parseInt(stream.substring(start, position)));
}
private Token nextName() {
final int start = position;
while (position < stream.length() &&
Character.isAlphabetic(stream.charAt(position))) {
++position;
}
return new Token(TokenType.NAME, start,
stream.substring(start, position));
}
private Token nextOperator() {
final int start = position;
while (position < stream.length()) {
final char ch = stream.charAt(position);
if (Character.isWhitespace(ch) ||
Character.isDigit(ch) ||
Character.isAlphabetic(ch) ||
ch == '(' || ch == ')' || ch == ',') {
break;
}
++position;
}
return new Token(TokenType.OPERATOR, start,
stream.substring(start, position));
}
private void error(Token token) {
throw new RuntimeException(
"Syntax error: unexpected token at column " +
(token.columnNumber+1) + " -- " + token.type.name() +
(token.payload == null ? "" : " (" + token.payload.toString() + ")"));
}
}

复制代码

magicsets

本帖最后由 magicsets 于 2018-1-12 13:30 编辑

biomedicineman 发表于 2018-1-12 12:13
intuit面试calculator题followup 3，要求带入variable

比如 given:

这个需要维护一个运行时环境（Runtime Environment），大概添加20行代码可以实现，参考下面代码的第34、35行。

此外，涉及到运行时环境的话，再加一点点代码就可以支持变量赋值了，然后再加一点点代码支持Multiple Statement，然后支持分支和循环，你就得到了一个小小的解释型程序语言... 再支持一下数组，这个语言就图灵完备了

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
// 一个使用样例
Calculator calc = new Calculator();
// 中间的数字是优先级（precedence），数字越小优先级越高
// 这里限定二元运算符是left associative，一元运算符是right associative
calc.registerOperation("+", 500, (a, b) -> a + b);
calc.registerOperation("-", 500, (a, b) -> a - b);
calc.registerOperation("*", 400, (a, b) -> a * b);
calc.registerOperation("/", 400, (a, b) -> a / b);
calc.registerOperation("^", 200, (a, b) -> (int) Math.pow(a, b));
calc.registerOperation("-", 100, (a) -> -a);
// 某道Calculator变形题，重定义了"&"和"|"的语义
calc.registerOperation("&", 600, (a, b) -> Math.max(a, b));
calc.registerOperation("|", 800, (a, b) -> Math.min(a, b));
// 也可以支持函数，函数本质上是前缀表达式，就不需要优先级信息了
calc.registerFunction("abs", (int ...a) -> Math.abs(a[0]));
calc.registerFunction("min", (int ...a) -> Arrays.stream(a).min().getAsInt());
calc.registerFunction("max", (int ...a) -> Arrays.stream(a).max().getAsInt());
System.out.println(calc.evaluate("1 + 2 * 3 ^ abs(6 - 3 * 3) + (-8) / (-2)"));
System.out.println(calc.evaluate("min(-3 * 2, -4, -5) * max(5, 6, 7, min(8, 9))"));
calc.setVariable("software", 3);
System.out.println(calc.evaluate("software * 2 + 1"));
}
}
/******************************************************************************
样例：使用下面的Solution类可以通过LeetCode 224
class Solution {
private static Calculator calc = new Calculator();
static {
calc.registerOperation("+", 500, (a, b) -> a + b);
calc.registerOperation("-", 500, (a, b) -> a - b);
calc.registerOperation("-", 100, (a) -> -a);
}
public int calculate(String s) {
return calc.evaluate(s);
}
}
******************************************************************************/
/******************************************************************************
样例：使用下面的Solution类可以通过LeetCode 227
class Solution {
private static Calculator calc = new Calculator();
static {
calc.registerOperation("+", 500, (a, b) -> a + b);
calc.registerOperation("-", 500, (a, b) -> a - b);
calc.registerOperation("*", 400, (a, b) -> a * b);
calc.registerOperation("/", 400, (a, b) -> a / b);
calc.registerOperation("-", 100, (a) -> -a);
}
public int calculate(String s) {
return calc.evaluate(s);
}
}
******************************************************************************/
class Calculator {
private Map<String, OperationInfo<UnaryOperation>> unaryOperations;
private Map<String, OperationInfo<BinaryOperation>> binaryOperations;
private Map<String, Function> functions;
private Map<String, Integer> environment;
public Calculator() {
this.unaryOperations =
new HashMap<String, OperationInfo<UnaryOperation>>();
this.binaryOperations =
new HashMap<String, OperationInfo<BinaryOperation>>();
this.functions = new HashMap<String, Function>();
this.environment = new HashMap<String, Integer>();
}
// 注册一个一元运算符
public void registerOperation(String operator, int precedence,
UnaryOperation operation) {
unaryOperations.put(
operator, new OperationInfo<UnaryOperation>(precedence, operation));
}
// 注册一个二元运算符
public void registerOperation(String operator, int precedence,
BinaryOperation operation) {
binaryOperations.put(
operator, new OperationInfo<BinaryOperation>(precedence, operation));
}
// 注册一个函数
public void registerFunction(String name, Function function) {
functions.put(name, function);
}
// 设置变量的值
public void setVariable(String name, int value) {
environment.put(name, value);
}
// 调用Executor对表达式进行计算
public int evaluate(String expression) {
CalculatorExecutor executor =
new CalculatorExecutor(unaryOperations, binaryOperations,
functions, environment, expression);
return executor.run();
}
}
// 对一元运算符的抽象
interface UnaryOperation {
public int apply(int operand);
}
// 对二元运算符的抽象
interface BinaryOperation {
public int apply(int lhs, int rhs);
}
// 对函数的抽象
interface Function {
public int apply(int ...operands);
}
// 用于打包operation和对应的precedence信息的小类
class OperationInfo<T> {
public final int precedence;
public final T operation;
public OperationInfo(int precedence, T operation) {
this.precedence = precedence;
this.operation = operation;
}
}
// LL(1) Recursive Descent Syntax Directed Translator
class CalculatorExecutor {
private final Map<String, OperationInfo<UnaryOperation>> unaryOperations;
private final Map<String, OperationInfo<BinaryOperation>> binaryOperations;
private final Map<String, Function> functions;
private Map<String, Integer> environment;
private final String stream;
private int position;
// 词法部分也合并到这个类里了
private enum TokenType {
INTEGER,
NAME,
OPERATOR,
LPAREN,
RPAREN,
COMMA,
EOS,
ERROR
}
private class Token {
public final TokenType type;
public final Object payload;
public final int columnNumber;
public Token(TokenType type, int columnNumber) {
this(type, columnNumber, null);
}
public Token(TokenType type, int columnNumber, Object payload) {
this.type = type;
this.payload = payload;
this.columnNumber = columnNumber;
}
}
private Stack<Token> tokens;
public CalculatorExecutor(
Map<String, OperationInfo<UnaryOperation>> unaryOperations,
Map<String, OperationInfo<BinaryOperation>> binaryOperations,
Map<String, Function> functions,
Map<String, Integer> environment,
String stream) {
this.unaryOperations = unaryOperations;
this.binaryOperations = binaryOperations;
this.functions = functions;
this.environment = environment;
this.stream = stream;
this.position = 0;
this.tokens = new Stack<Token>();
}
public int run() {
int value = evalExpr(Integer.MAX_VALUE);
passNextToken(TokenType.EOS);
return value;
}
//////////////////////////////////////////////////////////////////////////////
// 语法处理部分
private int evalExpr(int precedence) {
int value = evalFactor(precedence);
// 二元运算符，注意这里对优先级的处理方法
while (hasNextToken(TokenType.OPERATOR)) {
Token token = nextToken();
OperationInfo<BinaryOperation> info =
binaryOperations.get((String)token.payload);
if (info == null || info.precedence >= precedence) {
pushBack(token);
break;
}
value = info.operation.apply(value, evalExpr(info.precedence));
}
return value;
}
private int evalFactor(int precedence) {
Token token = nextToken();
// Case 1. 数字自身
if (token.type == TokenType.INTEGER) {
return (Integer)token.payload;
}
// Case 2. 一元运算符
if (token.type == TokenType.OPERATOR) {
OperationInfo<UnaryOperation> info =
unaryOperations.get((String)token.payload);
if (info == null || info.precedence > precedence) {
error(token);
}
return info.operation.apply(evalExpr(info.precedence));
}
// Case 3. 函数调用或者变量
if (token.type == TokenType.NAME) {
if (hasNextToken(TokenType.LPAREN)) {
Function func = functions.get((String)token.payload);
if (func == null) {
error(token);
}
ArrayList<Integer> args = new ArrayList<Integer>();
passNextToken(TokenType.LPAREN);
while (!hasNextToken(TokenType.RPAREN)) {
args.add(evalExpr(Integer.MAX_VALUE));
if (!hasNextToken(TokenType.COMMA)) {
break;
}
nextToken();
}
passNextToken(TokenType.RPAREN);
return func.apply(args.stream().mapToInt(x -> x).toArray());
} else {
String variable = (String)token.payload;
Integer value = environment.get(variable);
if (value == null) {
throw new RuntimeException(
"Undefined symbol " + variable + " at column " + token.columnNumber);
}
return value;
}
}
// Case 4. 括号表达式
if (token.type == TokenType.LPAREN) {
int value = evalExpr(Integer.MAX_VALUE);
Token rp = nextToken();
if (rp.type != TokenType.RPAREN) {
error(token);
}
return value;
}
error(token);
return 0;
}
//////////////////////////////////////////////////////////////////////////////
// 词法处理部分
private boolean hasNextToken(TokenType ...expected) {
Token token = nextToken();
boolean status = Arrays.stream(expected).anyMatch(x -> x == token.type);
pushBack(token);
return status;
}
private void passNextToken(TokenType ...expected) {
Token token = nextToken();
if (!Arrays.stream(expected).anyMatch(x -> x == token.type)) {
error(token);
}
}
private void pushBack(Token token) {
tokens.add(token);
}
private Token nextToken() {
if (!tokens.isEmpty()) {
return tokens.pop();
}
while (position < stream.length() &&
Character.isWhitespace(stream.charAt(position))) {
++position;
}
if (position >= stream.length()) {
return new Token(TokenType.EOS, position);
}
final int start = position;
final char ch = stream.charAt(position++);
switch (ch) {
case '(': return new Token(TokenType.LPAREN, start);
case ')': return new Token(TokenType.RPAREN, start);
case ',': return new Token(TokenType.COMMA, start);
default: --position; break;
}
if (Character.isDigit(ch)) {
return nextNumber();
}
if (Character.isAlphabetic(ch)) {
return nextName();
}
return nextOperator();
}
private Token nextNumber() {
final int start = position;
while (position < stream.length() &&
Character.isDigit(stream.charAt(position))) {
++position;
}
return new Token(TokenType.INTEGER, start,
Integer.parseInt(stream.substring(start, position)));
}
private Token nextName() {
final int start = position;
while (position < stream.length() &&
Character.isAlphabetic(stream.charAt(position))) {
++position;
}
return new Token(TokenType.NAME, start,
stream.substring(start, position));
}
private Token nextOperator() {
final int start = position;
while (position < stream.length()) {
final char ch = stream.charAt(position);
if (Character.isWhitespace(ch) ||
Character.isDigit(ch) ||
Character.isAlphabetic(ch) ||
ch == '(' || ch == ')' || ch == ',') {
break;
}
++position;
}
return new Token(TokenType.OPERATOR, start,
stream.substring(start, position));
}
private void error(Token token) {
throw new RuntimeException(
"Syntax error: unexpected token at column " +
(token.columnNumber+1) + " -- " + token.type.name() +
(token.payload == null ? "" : " (" + token.payload.toString() + ")"));
}
}

复制代码

biomedicineman

intuit面试calculator题followup 3，要求带入variable

比如 given:
String s = "software * 2 + 1"
Map: {"software" : 3}

那么需要求出3 * 2 + 1 = 7

biomedicineman

magicsets 发表于 2018-1-12 13:29
这个需要维护一个运行时环境（Runtime Environment），大概添加20行代码可以实现，参考下面代码的第34、3 ...

赞赞赞。

其实我刚才没说完。
intuit当时还有一个要求

比如String = "software + 2 * 3";
Map: {"hardware” ： 5}

也就是说会出现map里没有对应key的情况，那么就把能计算的算了，然后输出string
"software + 6"

magicsets

biomedicineman 发表于 2018-1-12 13:33
赞赞赞。

其实我刚才没说完。

这题目出得很偏啊 @_@，这个功能上和Calculator不是一回事了

比较系统的解决方案是生成语法树（Abstract Syntax Tree），然后求值所有不包含未定义变量的子树，然后再将折叠后的语法树输出为表达式

如果是改动我之前贴的代码的话，也可以进一步添加类型系统（Type System）以支持字符串和整数两种类型，这样的话诸如evalExpr()的返回值就不是int了，而是一个value union（常常写做TypedValue），类似于python object那种泛型变量。

然后求值时找不到变量的话就返回变量名的字符串；支持隐式类型转换以处理字符串和数字的运算。有点麻烦我就不写了...

magicsets

biomedicineman 发表于 2018-1-12 13:33
赞赞赞。

其实我刚才没说完。

谢谢大米

biomedicineman

magicsets 发表于 2018-1-12 13:53
这题目出得很偏啊 @_@，这个功能上和Calculator不是一回事了

比较系统的解决方案是生成语法树（Abstra ...

是啊是啊。最后那种情况压根就不是计算器了。。。所以我最后这个面试的时候没做出来。。。至今也没时间figure out

huorili

这个不给大米说不过去啊。。。太牛了

Calculator类题目的高级通用解法

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

评分

评分

评分

评分