pocket gems一面

basic calculator，有＋，－，＊，

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

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

！希望大家找工作顺利！

patpat 他家竟然换题了

LZ写出来了吗？这个临时写挺难的啊。。

lzyfriday 发表于 2015-11-13 07:16
LZ写出来了吗？这个临时写挺难的啊。。

写出来了，不过超时了。。coding之前聊了一刻钟，结束的时候发现面了一小时。。这个题走例子也费时间，我写完后自己主动走了一个例子，fix了一个bug，然后面试官给了一个更长的例子，又fix了一个bug。。

moyier 发表于 2015-11-13 07:23
写出来了，不过超时了。。coding之前聊了一刻钟，结束的时候发现面了一小时。。这个题走例子也费时间，我 ...

用两个stack做的吗？

水逼一枚 发表于 2015-11-13 07:28
用两个stack做的吗？

我就用了一个stack，遍历string的时候碰到数字、（就直接push；碰到＋、－就处理前一个运算直到stack空或者stack top是（，然后push结果和运算符；碰到＊、／要检查前一个运算，如果是＋、－就不处理，如果是＊、／就处理，push结果和运算符；碰到）就处理前一个运算，但是push结果之前要pop掉（

因为每次一边push一边在运算，所以保证了stack括号之间只有一个运算或只是一个数字，最后return之前也是。

已经被自己搞晕了。。

1. public class BasicCalculator {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 // TODO Auto-generated method stub
   
5.                 BasicCalculator solution = new BasicCalculator();
   
6.                 System.out.println(solution.calculate("( 1 + 8 ) - ( ( 3 * 4 ) / 2 )"));
   
7.         }
   
8.        
   
9.         /**
   
10.          * first transfer to RPN and then calculate the RPN
    
11.          * @param form
    
12.          * @return
    
13.          */
    
14.         public int calculate(String form){
    
15.                 ArrayList<String> polish = convertToRPN(form);
    
16.                 Stack<Integer> stack = new Stack<Integer>();
    
17.                 for(String token : polish){
    
18.                         switch(token){
    
19.                                 case "+":{
    
20.                                         stack.push(stack.pop() + stack.pop());
    
21.                                         break;
    
22.                                 }
    
23.                                 case "-":{
    
24.                                         int a = stack.pop();
    
25.                                         int b = stack.pop();
    
26.                                         stack.push(b - a);
    
27.                                         break;
    
28.                                 }
    
29.                                 case "*":{
    
30.                                         stack.push(stack.pop() * stack.pop());
    
31.                                         break;
    
32.                                 }
    
33.                                 case "/":{
    
34.                                         int a = stack.pop();
    
35.                                         int b = stack.pop();
    
36.                                         stack.push(b / a);
    
37.                                         break;
    
38.                                 }
    
39.                                 default:{
    
40.                                         stack.push(Integer.parseInt(token));
    
41.                                 }
    
42.                         }
    
43.                 }
    
44.                 return stack.peek();
    
45.         }
    
46.        
    
47.         /**
    
48.          * transfer the form to Reverse Polish Notation
    
49.          * @param form
    
50.          * @return
    
51.          */
    
52.         public ArrayList<String> convertToRPN(String form){
    
53.                 String[] tokens = form.split("\\s+");
    
54.                
    
55.                 ArrayList<String> out = new ArrayList<String>();
    
56.                 Stack<String> stack = new Stack();
    
57.                
    
58.                 for(String token : tokens){
    
59.                        
    
60.                         //add numbers to out stream direclty
    
61.                         if(!isOperator(token)){
    
62.                                 out.add(token);
    
63.                         }else{
    
64.                                 //if the token is ")", pop stack to out until meet "("
    
65.                                 //otherwise push the operator into stack
    
66.                                 if(!token.equals(")")){
    
67.                                         stack.push(token);
    
68.                                 }else{
    
69.                                         while(!stack.peek().equals("(")){
    
70.                                                 out.add(stack.pop());
    
71.                                         }
    
72.                                         stack.pop();
    
73.                                 }
    
74.                         }
    
75.                 }
    
76.                 while(!stack.isEmpty()){
    
77.                         out.add(stack.pop());
    
78.                 }
    
79.                
    
80.                 return out;
    
81.         }
    
82.         private boolean isOperator(String s){
    
83.                 return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("(") || s.equals(")");
    
84.         }
    
85. 
    
86. }
    

复制代码

先把式子转化成reverse polish notation, 然后解RPN

lzyfriday 发表于 2015-11-13 08:13
先把式子转化成reverse polish notation, 然后解RPN

中缀表达式转后缀表达式，之前没写过的话现场很难写出来吧，几个rules还是得强行记忆一下。

你好，请问下考不考虑负数的情况？
比如3 * -2 ？

我也贴一下我的代码。感觉这题非常难写对啊。不知道面起来怎么办。

1.         public static int calculate(String s) {
   
2.             if (s == null || s.length() == 0) return 0;
   
3.             Deque<Integer> stk = new LinkedList<Integer>();
   
4.             Deque<Character> chstk = new LinkedList<Character>();
   
5.             int num = 0;
   
6.             char sign = '+';
   
7.             int re = 0;
   
8.             for (int i = 0; i < s.length(); i++) {
   
9.                     char ch = s.charAt(i);
   
10.                     if (Character.isDigit(ch)) {
    
11.                             num = num * 10 + ch - '0';
    
12.                     }
    
13.                     if (ch == '*' || ch == '/') {
    
14.                             if (sign == '*') re *= num;
    
15.                             if (sign == '/') re /= num;
    
16.                             if (sign == '+' || sign == '-') { // push
    
17.                                     stk.push(re);
    
18.                                     chstk.push(sign);
    
19.                                     re = num;
    
20.                             }
    
21.                             sign = ch;
    
22.                             num = 0;
    
23.                     }
    
24.                     if (ch == '+' || ch =='-') {
    
25.                             if (sign == '+') re += num;
    
26.                             if (sign == '-') re -= num;
    
27.                             if (sign == '*' || sign == '/') { // pop
    
28.                                     if (sign == '*') re *= num;
    
29.                                     if (sign == '/') re /= num;
    
30.                                     char sg = chstk.pop();
    
31.                                     if (sg == '+') re = stk.pop() + re;
    
32.                                     if (sg == '-') re = stk.pop() - re;
    
33.                             }
    
34.                             sign = ch;
    
35.                             num = 0;
    
36.                     }
    
37.                     if (ch == '(') { // push
    
38.                             stk.push(re);
    
39.                             chstk.push(sign);
    
40.                             num = 0;
    
41.                             sign = '+';
    
42.                             re = 0;
    
43.                     }
    
44.                     if (ch == ')') { // pop
    
45.                             if (sign == '+') re += num;
    
46.                             if (sign == '-') re -= num;
    
47.                             if (sign == '*' || sign == '/') { // pop
    
48.                                     if (sign == '*') re *= num;
    
49.                                     if (sign == '/') re /= num;
    
50.                                     char sg = chstk.pop();
    
51.                                     if (sg == '+') re = stk.pop() + re;
    
52.                                     if (sg == '-') re = stk.pop() - re;
    
53.                             }
    
54.                             num = re;
    
55.                             sign = chstk.pop();
    
56.                             re = stk.pop();
    
57.                     }
    
58.             }
    
59.             if (stk.size() > 0) {
    
60.                     if (sign == '*') re *= num;
    
61.                     if (sign == '/') re /= num;
    
62.                     num = re;
    
63.                     sign = chstk.pop();
    
64.                     re = stk.pop();
    
65.             }
    
66.             if (num != 0) {
    
67.                     if (sign == '+') re += num;
    
68.                     if (sign == '-') re -= num;
    
69.                     if (sign == '*') re *= num;
    
70.                     if (sign == '/') re /= num;
    
71.             }
    
72.             return re;
    
73.         }

复制代码