昨天面试了一下，几个问题答不上来，特此求教小伙伴们

linfx7

2017-01-21 12:09:16 +08:00

第一道题用栈，（和数字入栈，遇到+-）出栈

b821025551b

2017-01-21 12:10:24 +08:00

第一道题的话，我的思路是：
1:排除含有数字和运算符之外的任何字符；
2:括号是否左右对称；
3:按照括号、乘除、加减这一优先级分组计算，计算前除数是否为 0 ；
4:继续 step3 ，直到分组只有 1 组，也就是最终结果。

bxb100

2017-01-21 12:13:05 +08:00

一楼正解

littlepanzh

2017-01-21 12:17:12 +08:00

第一题明显是考你数据结构，这是一道很基础的栈的题目吧。
第二题应该是和编译原理有关，而不是像你回答的 python 不需要考虑这个问题，这明显不是面试官想要的答案。
lz 还要继续加油啊

lcdtyph

2017-01-21 12:20:05 +08:00

第一题写出表达式的文法然后词法分析就好了
给一个 bnf 描述吧

expression = [ '+' | '-' ] term { ('+'|'-') term }
term = factor { ('*'|'/') factor}
factor = ident | number | '(' expression ')'

ident 是变量名， number 是立即数，不需要可以删掉
这样的好处是不需要计算就可以知道这个表达式是不是可计算的= =||
这个文法可以用递归下降直接写出来

cnilnhf

2017-01-21 12:21:35 +08:00

第一个问题用两个栈，最后看栈是否空。
第二个问题没看懂，是想问数组类的动态大小实现吗？（保持至少 1/2 元素，可是 Java 的数组是提前限定大小的)

gamexg

2017-01-21 13:26:12 +08:00

1.感觉最简单的只用判断"("、")"数量是否相等及 +-*/ 不允许连续出现就行，当然这个没考虑除以 0 。
2.不知道 python 是怎么实现的，某种实现是当空间不足时直接扩大一倍，下次不足继续扩大一倍空间。

nbndco

2017-01-21 14:25:31 +08:00

怎么把数组变成一个链表啊，你就算乱猜方向也不对……
其实就两招，一个是 C++ STL 里面的 vector （ python 也是），还一个就是 pre-allocate 全部了。
不过我不是很懂这个题，如果是顺序递增为何还要读入？整个过程和是否递增似乎也没有任何关系。

SpringHack

2017-01-21 14:56:10 +08:00

1. 逆波兰式
2. x2

iyaozhen

2017-01-21 15:55:46 +08:00

第一题应该是经典的括号匹配
第二题没太懂意思

kingfighters

2017-01-21 15:56:02 +08:00

谢谢楼上的小伙伴，第一个问题我最后说到了用栈，但是是是在面试官的一再提醒下，才回答出来的，确实应该是用逆波兰式。

第二个问题，确实如 SpringHack 和楼上的小伙伴提到的，应该是 X2 的关系，即没满了 2 的整数次方倍，就自动乘 2 。

acumen

2017-01-21 17:30:14 +08:00

ls 各位回答的都是逆波兰式，（第一反应是后缀表达式啊，百度一番才知道原来还有逼格这么高的学名。考的是数据结构吧，但是回答栈没毛病。

AccIdent

2017-01-21 17:48:14 +08:00

一百万的内存占用才Ｍ级别，当然不用考虑内存大小了，大概是想问类似于 Java 的 ArrayList

chiu

2017-01-21 18:22:01 +08:00

第一题，应该听过前缀、中缀、后缀表达式吧

Cbdy

2017-01-21 18:32:58 +08:00

第一题用正则是错误的，正则的表达能力不够。应该用带栈的自动机，即下推自动机。
第二题我也没看懂。

kkzxak47

2017-01-21 20:35:20 +08:00

如果是科班出身，第一题答不出来书是白念了。
第二题连题目都描述不清楚。
基础啊。

mayne95

2017-01-21 22:30:51 +08:00

如果我说第一题 exec 执行一下这个字符串会不会被打😂。

第二题说不考虑内存大小问题也就是可以 readlines 全部读入。 readlines 生成列表，列表的内存大小预先应该有个值，到了阈值之后再成倍扩大？

xielemon

2017-01-21 22:46:55 +08:00

第二问意思是 java 里 arraylist 存满了怎么扩容？大小 X2 吧

lalalanet

2017-01-21 22:55:19 +08:00

第二个问题，很简单

初始化数组，申请内存空间， 100 万 * 32 bit ，所有位全是 0
循环读入数据，每次改变 32bits 的内存
读取结束后， GC

脑补成 ArrayList 的，你们就记住 X2 了吧

billion

2017-01-21 23:15:44 +08:00

第一题：
try:
eval(字符串)
print('正确')
except Exception as _:
print('错误')