一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 558|回复: 10
收起左侧

pocket gems一面

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
basic calculator,有+,-,*,/,(,)。。。很费时,但面试官还和我一起走例子。。。
已跪了好几家了,心累。。。攒人品攒运气!希望大家找工作顺利!.鐣欏璁哄潧-涓浜-涓夊垎鍦

评分

1

查看全部评分

jzc007 发表于 2015-11-13 06:55:50 | 显示全部楼层
patpat 他家竟然换题了
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| moyier 发表于 2015-11-13 07:23:36 | 显示全部楼层
lzyfriday 发表于 2015-11-13 07:16
LZ写出来了吗?这个临时写挺难的啊。。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
写出来了,不过超时了。。coding之前聊了一刻钟,结束的时候发现面了一小时。。这个题走例子也费时间,我写完后自己主动走了一个例子,fix了一个bug,然后面试官给了一个更长的例子,又fix了一个bug。。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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.         }
  7.        
  8.         /**
  9.          * first transfer to RPN and then calculate the RPN
  10.          * @param form 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  11.          * @return
  12.          */
  13.         public int calculate(String form){
  14.                 ArrayList<String> polish = convertToRPN(form);
  15.                 Stack<Integer> stack = new Stack<Integer>();
  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 "*":{
  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:{
  39.                                         stack.push(Integer.parseInt(token));
  40.                                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  41.                         }
  42.                 }
  43.                 return stack.peek();
  44.         }
  45.        
  46.         /**
  47.          * transfer the form to Reverse Polish Notation
  48.          * @param form
  49.          * @return
  50.          */. more info on 1point3acres.com
  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){.1point3acres缃
  58.                        
  59.                         //add numbers to out stream direclty. visit 1point3acres.com for more.
  60.                         if(!isOperator(token)){
  61.                                 out.add(token);
  62.                         }else{. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  63.                                 //if the token is ")", pop stack to out until meet "("
  64.                                 //otherwise push the operator into stack. Waral 鍗氬鏈夋洿澶氭枃绔,
  65.                                 if(!token.equals(")")){
  66.                                         stack.push(token);
  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(")");. From 1point 3acres bbs
  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) {
  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 = '+';. visit 1point3acres.com for more.
  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 == '/') {. 1point3acres.com/bbs
  14.                             if (sign == '*') re *= num;
  15.                             if (sign == '/') re /= num;
  16.                             if (sign == '+' || sign == '-') { // push. 1point3acres.com/bbs
  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;. From 1point 3acres bbs
  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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  35.                             num = 0;
  36.                     }
  37.                     if (ch == '(') { // push
  38.                             stk.push(re);. 鍥磋鎴戜滑@1point 3 acres
  39.                             chstk.push(sign);. more info on 1point3acres.com
  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; . 1point3acres.com/bbs
  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.         }
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

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

custom counter

GMT+8, 2016-12-6 00:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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