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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2852 天前的主题，其中的信息可能已经有所发展或是发生改变。

如果有一个字符串，里面是数字（是否连续和个数不定），运算符号（加减乘除）同样是否连续或者个数也是不定，还有圆括号。怎么判断这个字符串是有效的，能得到运算结果的？

我想了一下，这个问题应该是考察编译原理的内容，词法解析，但是我做不出来。我想到的办法就是用正则表达式，但是很难把所有场景都想到。求教小伙伴该怎样回答这类问题？

第二个问题是，如果现在有一个大文件，比方说类似于 raw data 的，一行是一个数字，规律是递增，一共有 1 百万行，也就是说从 1 到 1 百万，现在如果需要全部读入内存，而且不考虑系统内存的大小，也就假定系统内存足够大。问题是，我们初始化了一个数组，然后往里面填充这一百万个数据，数组变量的内存变化是怎样的。

我想了一下，在 Python 里面根本不需要考虑这样的问题，我的回答是，可能 python 解释器在背后将这个数组变成了一个链表，面试我的人感觉对于这个回答不是特别满意。面试我的人直接用了一行 java 代码初始化了数组，我也对于 java 不熟悉。求教小伙伴怎样回答这个问题比较合适？

面试的是一家非常好的公司，面试的岗位是 Python 自动化开发。感谢小伙伴的时间。

Python

求教

面试

小伙伴

46 条回复 • 2018-05-16 21:43:44 +08:00

linfx7

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

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

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 via Android

一楼正解

littlepanzh

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

第一题明显是考你数据结构，这是一道很基础的栈的题目吧。
第二题应该是和编译原理有关，而不是像你回答的 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 via Android

第一个问题用两个栈，最后看栈是否空。
第二个问题没看懂，是想问数组类的动态大小实现吗？（保持至少 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 via Android

1. 逆波兰式
2. x2

iyaozhen

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

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

kingfighters

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

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

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

acumen

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

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

AccIdent

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

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

chiu

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

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

Cbdy

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

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

kkzxak47

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

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

mayne95

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

如果我说第一题 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('错误')

billion

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

@billion 晕，我的缩进被吃掉了。。。

Allianzcortex

2017-01-21 23:27:36 +08:00

@mayne95 exec() 不安全啊。第一道题是后缀表达式，用一个 List 模拟堆栈存储数字和括号，用另一个 List 模拟存储符号，遇到右括号就弹出计算最近的两个数字值。第二道题有毒，，它是要考 Young Generation 的 GC 机制还是什么。 @xielemon @lalalanet 呃。。我记得 ArrayList 的 capacity growth 根据实现机制的细节是不一样的，应该是原有的 *1.5 后再 +1 （很久以前在 SO 上看的一个回答了，现在手机答，不确保对不对。。。）

zhuangzhuang1988

2017-01-21 23:49:43 +08:00

第二题依赖具体实现的。。

wy315700

2017-01-22 00:22:02 +08:00

如果我没记错的话， Python 里面存储整数的时候， 0-255 和其他数是不一样的吧。

owt5008137

2017-01-22 04:27:38 +08:00 via Android

第一个直接用栈跑一遍运算就好了。不涉及编译原理。如果最后栈 pop 不完那就是不合法的表达式
第二个假设你是一行一行读入，并且没有内存浪费。那么看你用什么数据结构去存。如果是那种有预分配的数据结构，那么增长点就是每次 reserve 的时候。如果是链表或者直接数组，那么增长点是每次触发物理内存页映射到虚拟地址上。大多数环境是每次涨 4KB （分页大小）

q397064399

2017-01-22 07:17:10 +08:00

第一题，确实是编译原理相关，但是跟词法解析没有关系，一般词法解析是采用递归下降的文法，
这题问的应该是最著名的逆波兰表达式算法第四版有讲这个不难，
因为比较著名，很多人都知道，所以考的是你的知识的广度
两个栈就能搞定，不过我记不起来，书上我有笔记，随时可以扒下来

第二题，数组相关，线性连续的数据结构只有一种方式，扩大-拷贝没有其它办法，早期 C++的 vector 就是采用
数组扩大一倍然后拷贝过去，底层绝不是通过数组+链表实现因为数组是要随机访问的，
如果加入了链表组合+数组实现（我傻逼的实现过，后来考虑到效率确实低），那么每次随机访问都要做 O(N)次操作来确定是当前随机位置在哪个数组中

xielemon

2017-01-22 09:29:46 +08:00

@Allianzcortex 确实是，我记错了

wizardoz

2017-01-22 09:49:57 +08:00

第一题是转逆波兰式,转的过程就知道正确性了.
第二题不懂,对 python 的实现不是很了解.

20015jjw

2017-01-22 10:19:28 +08:00 via Android

我都没听过逆波兰式... 我是怎么面过这些公司的...

yeyuexia

2017-01-22 11:28:36 +08:00

第二题我没记错的话 list 所占内存每次满的时候扩充一倍

WangYanjie

2017-01-22 11:47:04 +08:00

其实楼主是吃了基础不扎实的亏，

hanbing135

2017-01-22 12:19:55 +08:00 via Android

lz 的基础知识面太虚了

luw2007

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

列表内存增加：
https://github.com/python/cpython/blob/2.7/Objects/listobject.c

* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);