FB实习二面跪经

刚刚的FB实习二面跪经，运气不太好，之前地理的面经，LC的tag都做了。没想到来了一个后来才发现是而而思 计算器的变种，in

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

实习给个这么难的，哎。还是得好好刷题吧，200道还是不够。

用两个栈进行计算，一个存储数字一个存储符号，入栈的符号优先级低于栈顶符号时，将所有高于的符号出栈然后计算，遇到反括号就不停出栈计算直到遇到正括号。 可以把这个过程想象成一个简单的语法树。。

继续找吧，LZ这么认真一定能找到的。

顺序扫string，maintain一个toAdd和toMultiply，toAdd一开始是0，toMultiply一开始是1，具体更新方法和lc 282 (Expression add operator)一样。关于括号，遇到开括号直接递归call，遇到反括号直接return当前结果

递归后得想办法更新当前string的index，可以用global variable

会有好运气的！
楼主是店面还是uday呀！

这个题lintcode上有，算是很难的题了，楼主加油～

这个确实是hard, 保持一个increasing  stack, 对不同符号定义不同优先级。具体去lintcode 看看

这边有一份支持“自定义操作符”的代码，LZ可以参考学习一下...

第13到22行的代码写出来是可以impress住面试官的，基本上所有Calculator的变形题都可以通过改这几行处理（如果要处理浮点类型则要稍微改一下nextNumber()函数）。

1. import java.util.ArrayList;
   
2. import java.util.Arrays;
   
3. import java.util.HashMap;
   
4. import java.util.Map;
   
5. import java.util.Stack;
   
6. 
   
7. public class Main {
   
8.   public static void main(String[] args) {
   
9.     Calculator calc = new Calculator();
   
10. 
    
11.     // 中间的数字是优先级（precedence），数字越小优先级越高
    
12.     // 这里限定二元运算符是left associative，一元运算符是right associative
    
13.     calc.registerOperation("+", 500, (a, b) -> a + b);
    
14.     calc.registerOperation("-", 500, (a, b) -> a - b);
    
15.     calc.registerOperation("*", 400, (a, b) -> a * b);
    
16.     calc.registerOperation("/", 400, (a, b) -> a / b);
    
17.     calc.registerOperation("**", 200, (a, b) -> (int) Math.pow(a, b));
    
18.     calc.registerOperation("-", 100, (a) -> -a);
    
19. 
    
20.     calc.registerFunction("abs", (int ...a) -> Math.abs(a[0]));
    
21.     calc.registerFunction("min", (int ...a) -> Math.min(a[0], a[1]));
    
22.     calc.registerFunction("max", (int ...a) -> Math.max(a[0], a[1]));
    
23. 
    
24.     System.out.println(calc.evaluate("1 + 2 * 3 ** abs(6 - 3 * 3) + (-8) / (-2)"));
    
25.     System.out.println(calc.evaluate("min(-3 * 2, -4) * max(5, 6)"));
    
26.   }
    
27. }
    
28. 
    
29. /******************************************************************************
    
30. 样例：使用下面的Solution类可以通过LeetCode 224
    
31. 
    
32. class Solution {
    
33.   private static Calculator calc = new Calculator();
    
34.   static {
    
35.     calc.registerOperation("+", 500, (a, b) -> a + b);
    
36.     calc.registerOperation("-", 500, (a, b) -> a - b);
    
37.     calc.registerOperation("-", 100, (a) -> -a);
    
38.   }
    
39. 
    
40.   public int calculate(String s) {
    
41.     return calc.evaluate(s);
    
42.   }
    
43. }
    
44. 
    
45. ******************************************************************************/
    
46. 
    
47. /******************************************************************************
    
48. 样例：使用下面的Solution类可以通过LeetCode 227
    
49. 
    
50. class Solution {
    
51.   private static Calculator calc = new Calculator();
    
52.   static {
    
53.     calc.registerOperation("+", 500, (a, b) -> a + b);
    
54.     calc.registerOperation("-", 500, (a, b) -> a - b);
    
55.     calc.registerOperation("*", 400, (a, b) -> a * b);
    
56.     calc.registerOperation("/", 400, (a, b) -> a / b);
    
57.     calc.registerOperation("-", 100, (a) -> -a);
    
58.   }
    
59. 
    
60.   public int calculate(String s) {
    
61.     return calc.evaluate(s);
    
62.   }
    
63. }
    
64. 
    
65. ******************************************************************************/
    
66. 
    
67. class Calculator {
    
68.   private Map<String, OperationInfo<UnaryOperation>> unaryOperations;
    
69.   private Map<String, OperationInfo<BinaryOperation>> binaryOperations;
    
70.   private Map<String, Function> functions;
    
71. 
    
72.   public Calculator() {
    
73.     this.unaryOperations =
    
74.         new HashMap<String, OperationInfo<UnaryOperation>>();
    
75.     this.binaryOperations =
    
76.         new HashMap<String, OperationInfo<BinaryOperation>>();
    
77.     this.functions = new HashMap<String, Function>();
    
78.   }
    
79. 
    
80.   // 注册一个一元运算符
    
81.   public void registerOperation(String operator, int precedence,
    
82.                                 UnaryOperation operation) {
    
83.     unaryOperations.put(
    
84.         operator, new OperationInfo<UnaryOperation>(precedence, operation));
    
85.   }
    
86. 
    
87.   // 注册一个二元运算符
    
88.   public void registerOperation(String operator, int precedence,
    
89.                                 BinaryOperation operation) {
    
90.     binaryOperations.put(
    
91.         operator, new OperationInfo<BinaryOperation>(precedence, operation));
    
92.   }
    
93. 
    
94.   // 注册一个函数
    
95.   public void registerFunction(String name, Function function) {
    
96.     functions.put(name, function);
    
97.   }
    
98. 
    
99.   // 调用Executor对表达式进行计算
    
100.   public int evaluate(String expression) {
     
101.     CalculatorExecutor executor =
     
102.         new CalculatorExecutor(unaryOperations, binaryOperations,
     
103.                                functions, expression);
     
104.     return executor.run();
     
105.   }
     
106. }
     
107. 
     
108. 
     
109. // 对一元运算符的抽象
     
110. interface UnaryOperation {
     
111.   public int apply(int operand);
     
112. }
     
113. 
     
114. // 对二元运算符的抽象
     
115. interface BinaryOperation  {
     
116.   public int apply(int operand1, int operand2);
     
117. }
     
118. 
     
119. // 对函数的抽象
     
120. interface Function {
     
121.   public int apply(int ...operands);
     
122. }
     
123. 
     
124. 
     
125. // 用于打包operation和对应的precedence信息的小类
     
126. class OperationInfo<OpType> {
     
127.   public final int precedence;
     
128.   public final OpType operation;
     
129.   public OperationInfo(int precedence, OpType operation) {
     
130.     this.precedence = precedence;
     
131.     this.operation = operation;
     
132.   }
     
133. }
     
134. 
     
135. // LL(1) Recursive Descent Syntax Directed Translator
     
136. class CalculatorExecutor {
     
137.   private final Map<String, OperationInfo<UnaryOperation>> unaryOperations;
     
138.   private final Map<String, OperationInfo<BinaryOperation>> binaryOperations;
     
139.   private final Map<String, Function> functions;
     
140. 
     
141.   private final String stream;
     
142.   private int position;
     
143. 
     
144.   // 词法部分也合并到这个类里了
     
145.   private enum TokenType {
     
146.     INTEGER,
     
147.     NAME,
     
148.     OPERATOR,
     
149.     LPAREN,
     
150.     RPAREN,
     
151.     COMMA,
     
152.     EOS,
     
153.     ERROR
     
154.   }
     
155. 
     
156.   private class Token {
     
157.     public final TokenType type;
     
158.     public final Object payload;
     
159.     public final int columnNumber;
     
160.     public Token(TokenType type, int columnNumber) {
     
161.       this(type, columnNumber, null);
     
162.     }
     
163.     public Token(TokenType type, int columnNumber, Object payload) {
     
164.       this.type = type;
     
165.       this.payload = payload;
     
166.       this.columnNumber = columnNumber;
     
167.     }
     
168.   }
     
169. 
     
170.   private Stack<Token> tokens;
     
171. 
     
172.   public CalculatorExecutor(
     
173.       Map<String, OperationInfo<UnaryOperation>> unaryOperations,
     
174.       Map<String, OperationInfo<BinaryOperation>> binaryOperations,
     
175.       Map<String, Function> functions,
     
176.       String stream) {
     
177.     this.unaryOperations = unaryOperations;
     
178.     this.binaryOperations = binaryOperations;
     
179.     this.functions = functions;
     
180.     this.stream = stream;
     
181.     this.position = 0;
     
182.     this.tokens = new Stack<Token>();
     
183.   }
     
184. 
     
185.   public int run() {
     
186.     int value = evalExpr(Integer.MAX_VALUE);
     
187.     passNextToken(TokenType.EOS);
     
188.     return value;
     
189.   }
     
190. 
     
191.   private int evalExpr(int precedence) {
     
192.     int value = evalFactor(precedence);
     
193. 
     
194.     while (hasNextToken(TokenType.OPERATOR)) {
     
195.       Token token = nextToken();
     
196.       OperationInfo<BinaryOperation> info =
     
197.           binaryOperations.get((String)token.payload);
     
198.       if (info == null || info.precedence >= precedence) {
     
199.         pushBack(token);
     
200.         break;
     
201.       }
     
202.       value = info.operation.apply(value, evalExpr(info.precedence));
     
203.     }
     
204.     return value;
     
205.   }
     
206. 
     
207.   private int evalFactor(int precedence) {
     
208.     Token token = nextToken();
     
209. 
     
210.     if (token.type == TokenType.INTEGER) {
     
211.       return (Integer)token.payload;
     
212.     }
     
213. 
     
214.     if (token.type == TokenType.OPERATOR) {
     
215.       OperationInfo<UnaryOperation> info =
     
216.           unaryOperations.get((String)token.payload);
     
217.       if (info == null || info.precedence > precedence) {
     
218.         error(token);
     
219.       }
     
220.       return info.operation.apply(evalExpr(info.precedence));
     
221.     }
     
222. 
     
223.     if (token.type == TokenType.NAME) {
     
224.       Function func = functions.get((String)token.payload);
     
225.       if (func == null) {
     
226.         error(token);
     
227.       }
     
228.       ArrayList<Integer> args = new ArrayList<Integer>();
     
229.       passNextToken(TokenType.LPAREN);
     
230.       while (!hasNextToken(TokenType.RPAREN)) {
     
231.         args.add(evalExpr(Integer.MAX_VALUE));
     
232.         if (!hasNextToken(TokenType.COMMA)) {
     
233.           break;
     
234.         }
     
235.         nextToken();
     
236.       }
     
237.       passNextToken(TokenType.RPAREN);
     
238.       return func.apply(args.stream().mapToInt(x -> x).toArray());
     
239.     }
     
240. 
     
241.     if (token.type == TokenType.LPAREN) {
     
242.       int value = evalExpr(Integer.MAX_VALUE);
     
243.       Token rp = nextToken();
     
244.       if (rp.type != TokenType.RPAREN) {
     
245.         error(token);
     
246.       }
     
247.       return value;
     
248.     }
     
249. 
     
250.     error(token);
     
251.     return 0;
     
252.   }
     
253. 
     
254.   private boolean hasNextToken(TokenType ...expected) {
     
255.     Token token = nextToken();
     
256.     boolean status = Arrays.stream(expected).anyMatch(x -> x == token.type);
     
257.     pushBack(token);
     
258.     return status;
     
259.   }
     
260. 
     
261.   private void passNextToken(TokenType ...expected) {
     
262.     Token token = nextToken();
     
263.     if (!Arrays.stream(expected).anyMatch(x -> x == token.type)) {
     
264.       error(token);
     
265.     }
     
266.   }
     
267. 
     
268.   private void pushBack(Token token) {
     
269.     tokens.add(token);
     
270.   }
     
271. 
     
272.   private Token nextToken() {
     
273.     if (!tokens.isEmpty()) {
     
274.       return tokens.pop();
     
275.     }
     
276.     while (position < stream.length() &&
     
277.            Character.isWhitespace(stream.charAt(position))) {
     
278.       ++position;
     
279.     }
     
280. 
     
281.     if (position >= stream.length()) {
     
282.       return new Token(TokenType.EOS, position);
     
283.     }
     
284. 
     
285.     final int start = position;
     
286.     final char ch = stream.charAt(position++);
     
287. 
     
288.     switch (ch) {
     
289.       case '(': return new Token(TokenType.LPAREN, start);
     
290.       case ')': return new Token(TokenType.RPAREN, start);
     
291.       case ',': return new Token(TokenType.COMMA, start);
     
292.       default:  --position; break;
     
293.     }
     
294. 
     
295.     if (Character.isDigit(ch)) {
     
296.       return nextNumber();
     
297.     }
     
298.     if (Character.isAlphabetic(ch)) {
     
299.       return nextName();
     
300.     }
     
301.     return nextOperator();
     
302.   }
     
303. 
     
304.   private Token nextNumber() {
     
305.     final int start = position;
     
306.     while (position < stream.length() &&
     
307.            Character.isDigit(stream.charAt(position))) {
     
308.       ++position;
     
309.     }
     
310.     return new Token(TokenType.INTEGER, start,
     
311.                      Integer.parseInt(stream.substring(start, position)));
     
312.   }
     
313. 
     
314.   private Token nextName() {
     
315.     final int start = position;
     
316.     while (position < stream.length() &&
     
317.            Character.isAlphabetic(stream.charAt(position))) {
     
318.       ++position;
     
319.     }
     
320.     return new Token(TokenType.NAME, start,
     
321.                      stream.substring(start, position));
     
322.   }
     
323. 
     
324.   private Token nextOperator() {
     
325.     final int start = position;
     
326.     while (position < stream.length()) {
     
327.       final char ch = stream.charAt(position);
     
328.       if (Character.isWhitespace(ch) ||
     
329.           Character.isDigit(ch) ||
     
330.           Character.isAlphabetic(ch) ||
     
331.           ch == '(' || ch == ')' || ch == ',') {
     
332.         break;
     
333.       }
     
334.       ++position;
     
335.     }
     
336.     return new Token(TokenType.OPERATOR, start,
     
337.                      stream.substring(start, position));
     
338.   }
     
339. 
     
340.   private void error(Token token) {
     
341.     throw new RuntimeException(
     
342.         "Syntax error: unexpected token at column " +
     
343.         (token.columnNumber+1) + " -- " + token.type.name() +
     
344.         (token.payload == null ? "" : " (" + token.payload.toString() + ")"));
     
345.   }
     
346. }
     

复制代码

patpat,这题我记得pocketgems 喜欢考，还有一位大佬总结了所有的计算器变形来着。