Zenefits 电面

印度人

有点像 reverse polish notation 的变种，计算一个表达式的值的。要求自行设计表达式的数据结构并计算表达式的值。

有几种特殊情况

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
resssion 的List，再用一个Queue来决定问题。不知道有没有大神有更好的做法。



面完收到要求第二轮电面的邮件，有没有大神知道这是什么意思？是面得不太好吗？

1. class Solution:
   
2. 
   
3.     def eval(self, expr):
   
4.         operator = expr[0]
   
5.         expr = expr[1:]
   
6.         evaled_expr = []
   
7.         for it in expr:
   
8.             if isinstance(it, list):
   
9.                 evaled = self.eval(it)
   
10.                 evaled_expr.append(evaled)
    
11.             else:
    
12.                 evaled_expr.append(it)
    
13.         res = 0
    
14.         if operator == '+':
    
15.             res = sum(evaled_expr)
    
16.         elif operator == '*':
    
17.             res = 1
    
18.             for it in evaled_expr:
    
19.                 res *= it
    
20.         elif operator == '-':
    
21.             res = evaled_expr[0] if len(evaled_expr) > 0 else 0
    
22.             for it in evaled_expr[1:]:
    
23.                 res -= it
    
24.         elif operator == '/':
    
25.             res = evaled_expr[0] if len(evaled_expr) > 0 else 0
    
26.             for it in evaled_expr[1:]:
    
27.                 res /= it
    
28.         return res
    

复制代码

Test Cases:

1. import unittest
   
2. from solution import Solution
   
3. 
   
4. 
   
5. class Test(unittest.TestCase):
   
6. 
   
7.     def test1(self):
   
8.         s = Solution()
   
9.         expr = ['+', 1, 2, ['*', 1, 3]]
   
10.         res = s.eval(expr)
    
11.         self.assertEqual(res, 6)
    
12. 
    
13.     def test2(self):
    
14.         s = Solution()
    
15.         expr = ['+', 1, 2, ['*', 2, 3]]
    
16.         res = s.eval(expr)
    
17.         self.assertEqual(res, 9)
    
18. 
    
19.     def test3(self):
    
20.         s = Solution()
    
21.         expr = ['+', ['*'], ['-'], ['/']]
    
22.         res = s.eval(expr)
    
23.         self.assertEqual(res, 1)
    
24. 
    
25.     def test4(self):
    
26.         s = Solution()
    
27.         expr = ['+', 1, 2, ['*', 2, 3], ['-', 4, 5], ['/', 8, 2]]
    
28.         res = s.eval(expr)
    
29.         self.assertEqual(res, 12)
    
30. 
    
31. if __name__ == '__main__':
    
32.     unittest.main(verbosity=2)
    

复制代码

没太想明白楼主的做法，我的想法跟johnnywsd 的类似，不过python我不熟，我用java的话就是这样一个class
class Expression{
char operator;
list<double> numbers;
list<Expression> innerExpression;
...
}

但是这样比较麻烦的是需要有一个parser 把类似 [+, 1, 2, 3, [*, 2, 3], 6]  的输入变成一个object

我没想明白怎么用“Expresssion 的List，再用一个Queue来决定问题”，我这种定义class的方法，貌似一个object就足够了

ManitobaFarmer 发表于 2015-5-1 11:10
你愿意写成 String[] 的形式也可以，数据结构随便设计，能计算这么个 expression 的值就行。

我知道，我的意思是这个expression里面是否用中括号区分了不同的嵌套部分，还是没有中括号只靠字符去区分？

第四种情况应该是1 + 2 + 1 * 3 = 6 吧

GatherNone 发表于 2015-5-1 07:59
第四种情况应该是1 + 2 + 1 * 3 = 6 吧

恩，打错了，不好意思。

楼主，这个原始的输入带那个中括号吗？

xieqilu1989 发表于 2015-5-1 11:04
楼主，这个原始的输入带那个中括号吗？

你愿意写成 String[] 的形式也可以，数据结构随便设计，能计算这么个 expression 的值就行。

xieqilu1989 发表于 2015-5-1 11:23
我知道，我的意思是这个expression里面是否用中括号区分了不同的嵌套部分，还是没有中括号只靠字符去区分 ...

自己想办法解决。逻辑上是有个中括号区分的，怎么实现就是面试者要处理的问题。

ManitobaFarmer 发表于 2015-5-1 11:27
自己想办法解决。逻辑上是有个中括号区分的，怎么实现就是面试者要处理的问题。

明白了！多谢啦！

那么，类似于[+, 1, 2, 3, [*, 2, 3], 6] 这种算合法输入么？
如果不算的话，我觉得逆序处理list比较简单吧
[+, 1, 2, 3, *, 2, 3, 6]  => [+, 1, 2, 3, 36] => 42

ShadowChaser 发表于 2015-5-1 12:28
那么，类似于[+, 1, 2, 3, [*, 2, 3], 6] 这种算合法输入么？
如果不算的话，我觉得逆序处理list比较简单 ...

算，结果是 1 + 2 + 3 + (2 * 3) + 6 = 18