May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1454|回复: 10
收起左侧

pocket gems一面

[复制链接] |试试Instant~ |关注本帖
moyier 发表于 2015-11-13 06:52:12 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@PoketGem - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
basic calculator,有+,-,*,/,(,)。。。很费时,但面试官还和我一起走例子。。。
已跪了好几家了,心累。。。攒人品攒运气!希望大家找工作顺利!
. from: 1point3acres.com/bbs

评分

1

查看全部评分

jzc007 发表于 2015-11-13 06:55:50 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
patpat 他家竟然换题了
回复 支持 反对

使用道具 举报

lzyfriday 发表于 2015-11-13 07:16:57 | 显示全部楼层
关注一亩三分地微博:
Warald
LZ写出来了吗?这个临时写挺难的啊。。
回复 支持 反对

使用道具 举报

 楼主| moyier 发表于 2015-11-13 07:23:36 | 显示全部楼层
lzyfriday 发表于 2015-11-13 07:16
LZ写出来了吗?这个临时写挺难的啊。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
写出来了,不过超时了。。coding之前聊了一刻钟,结束的时候发现面了一小时。。这个题走例子也费时间,我写完后自己主动走了一个例子,fix了一个bug,然后面试官给了一个更长的例子,又fix了一个bug。。
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-11-13 07:28:29 | 显示全部楼层
moyier 发表于 2015-11-13 07:23. from: 1point3acres.com/bbs
写出来了,不过超时了。。coding之前聊了一刻钟,结束的时候发现面了一小时。。这个题走例子也费时间,我 ...

用两个stack做的吗?
回复 支持 反对

使用道具 举报

 楼主| moyier 发表于 2015-11-13 07:56:07 | 显示全部楼层
水逼一枚 发表于 2015-11-13 07:28
用两个stack做的吗?

我就用了一个stack,遍历string的时候碰到数字、(就直接push;碰到+、-就处理前一个运算直到stack空或者stack top是(,然后push结果和运算符;碰到*、/要检查前一个运算,如果是+、-就不处理,如果是*、/就处理,push结果和运算符;碰到)就处理前一个运算,但是push结果之前要pop掉(

因为每次一边push一边在运算,所以保证了stack括号之间只有一个运算或只是一个数字,最后return之前也是。. From 1point 3acres bbs

已经被自己搞晕了。。
回复 支持 反对

使用道具 举报

lzyfriday 发表于 2015-11-13 08:13:31 | 显示全部楼层
  1. public class BasicCalculator {

  2.         public static void main(String[] args) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  3.                 // TODO Auto-generated method stub
  4.                 BasicCalculator solution = new BasicCalculator();
  5.                 System.out.println(solution.calculate("( 1 + 8 ) - ( ( 3 * 4 ) / 2 )"));
  6.         }. 1point3acres.com/bbs
  7.        
  8.         /**
  9.          * first transfer to RPN and then calculate the RPN
  10.          * @param form. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  11.          * @return 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  12.          */. visit 1point3acres.com for more.
  13.         public int calculate(String form){
  14.                 ArrayList<String> polish = convertToRPN(form);
  15.                 Stack<Integer> stack = new Stack<Integer>();. From 1point 3acres bbs
  16.                 for(String token : polish){
  17.                         switch(token){
  18.                                 case "+":{
  19.                                         stack.push(stack.pop() + stack.pop());
  20.                                         break;
  21.                                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  22.                                 case "-":{
  23.                                         int a = stack.pop();
  24.                                         int b = stack.pop();
  25.                                         stack.push(b - a);
  26.                                         break;
  27.                                 }
  28.                                 case "*":{.鏈枃鍘熷垱鑷1point3acres璁哄潧
  29.                                         stack.push(stack.pop() * stack.pop());
  30.                                         break;
  31.                                 }
  32.                                 case "/":{
  33.                                         int a = stack.pop();
  34.                                         int b = stack.pop();
  35.                                         stack.push(b / a);
  36.                                         break;
  37.                                 }
  38.                                 default:{. visit 1point3acres.com for more.
  39.                                         stack.push(Integer.parseInt(token));
  40.                                 }
  41.                         }
  42.                 }
  43.                 return stack.peek();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  44.         }
  45.         -google 1point3acres
  46.         /**
  47.          * transfer the form to Reverse Polish Notation
  48.          * @param form
  49.          * @return
  50.          */
  51.         public ArrayList<String> convertToRPN(String form){
  52.                 String[] tokens = form.split("\\s+");
  53.                
  54.                 ArrayList<String> out = new ArrayList<String>();
  55.                 Stack<String> stack = new Stack();
  56.                
  57.                 for(String token : tokens){
  58.                        
  59.                         //add numbers to out stream direclty
  60.                         if(!isOperator(token)){
  61.                                 out.add(token);. Waral 鍗氬鏈夋洿澶氭枃绔,
  62.                         }else{. visit 1point3acres.com for more.
  63.                                 //if the token is ")", pop stack to out until meet "("
  64.                                 //otherwise push the operator into stack
  65.                                 if(!token.equals(")")){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  66.                                         stack.push(token);. visit 1point3acres.com for more.
  67.                                 }else{
  68.                                         while(!stack.peek().equals("(")){
  69.                                                 out.add(stack.pop());. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  70.                                         }
  71.                                         stack.pop();
  72.                                 }
  73.                         }
  74.                 }
  75.                 while(!stack.isEmpty()){
  76.                         out.add(stack.pop());
  77.                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  78.                
  79.                 return out;
  80.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  81.         private boolean isOperator(String s){
  82.                 return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("(") || s.equals(")");
  83.         }

  84. }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
复制代码


先把式子转化成reverse polish notation, 然后解RPN
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-11-13 08:26:59 | 显示全部楼层
lzyfriday 发表于 2015-11-13 08:13
先把式子转化成reverse polish notation, 然后解RPN

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

使用道具 举报

甯甯 发表于 2015-11-18 12:13:13 | 显示全部楼层
你好,请问下考不考虑负数的情况?
比如3 * -2 ?
回复 支持 反对

使用道具 举报

甯甯 发表于 2015-11-18 14:29:05 | 显示全部楼层
我也贴一下我的代码。感觉这题非常难写对啊。不知道面起来怎么办。
  1.         public static int calculate(String s) {. 1point 3acres 璁哄潧
  2.             if (s == null || s.length() == 0) return 0;. more info on 1point3acres.com
  3.             Deque<Integer> stk = new LinkedList<Integer>();
  4.             Deque<Character> chstk = new LinkedList<Character>();. From 1point 3acres bbs
  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';. 1point 3acres 璁哄潧
  12.                     }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13.                     if (ch == '*' || ch == '/') {
  14.                             if (sign == '*') re *= num;
  15.                             if (sign == '/') re /= num;
  16.                             if (sign == '+' || sign == '-') { // push. 鍥磋鎴戜滑@1point 3 acres
  17.                                     stk.push(re);
  18.                                     chstk.push(sign);-google 1point3acres
  19.                                     re = num;
  20.                             }
  21.                             sign = ch;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.                     }. from: 1point3acres.com/bbs
  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. From 1point 3acres bbs
  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.                             }. From 1point 3acres bbs
  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;. From 1point 3acres bbs
  68.                     if (sign == '-') re -= num;
  69.                     if (sign == '*') re *= num;
  70.                     if (sign == '/') re /= num;. more info on 1point3acres.com
  71.             }
  72.             return re;.1point3acres缃
  73.         }
复制代码
回复 支持 反对

使用道具 举报

 楼主| moyier 发表于 2015-11-19 07:57:55 | 显示全部楼层
甯甯 发表于 2015-11-18 14:29
我也贴一下我的代码。感觉这题非常难写对啊。不知道面起来怎么办。

已跪估计有些地方考虑得不够周全,当时一听题目就有不好的感觉了
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-5-25 02:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表