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

V2EX = way to explore

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

For Existing Member Sign In

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

This topic created in 3385 days ago, the information mentioned may be changed or developed.

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

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

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

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

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

Python

求教

面试

小伙伴

46 replies • 2018-05-16 21:43:44 +08:00

linfx7

Jan 21, 2017 via iPhone

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

b821025551b

Jan 21, 2017

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

bxb100

Jan 21, 2017 via Android

一楼正解

littlepanzh

Jan 21, 2017 via iPhone

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

lcdtyph

Jan 21, 2017

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

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

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

cnilnhf

Jan 21, 2017 via Android

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

gamexg

Jan 21, 2017

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

nbndco

Jan 21, 2017

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

SpringHack

Jan 21, 2017 via Android

1. 逆波兰式
2. x2

iyaozhen

Jan 21, 2017 via Android

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

kingfighters

Jan 21, 2017

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

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

acumen

Jan 21, 2017 via iPhone

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

AccIdent

Jan 21, 2017

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

chiu

Jan 21, 2017 via Android

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

Cbdy

Jan 21, 2017 via Android

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

kkzxak47

Jan 21, 2017 via Android

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

mayne95

Jan 21, 2017 via Android

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

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

xielemon

Jan 21, 2017

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

lalalanet

Jan 21, 2017

第二个问题，很简单

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

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

billion

Jan 21, 2017

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

billion

Jan 21, 2017

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

Allianzcortex

Jan 21, 2017

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

zhuangzhuang1988

Jan 21, 2017

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

wy315700

Jan 22, 2017

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

owt5008137

Jan 22, 2017 via Android

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

q397064399

Jan 22, 2017

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

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

xielemon

Jan 22, 2017

@Allianzcortex 确实是，我记错了

wizardoz

Jan 22, 2017

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

20015jjw

Jan 22, 2017 via Android

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

yeyuexia

Jan 22, 2017

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

WangYanjie

Jan 22, 2017

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

hanbing135

Jan 22, 2017 via Android

lz 的基础知识面太虚了

luw2007

Jan 22, 2017

列表内存增加：
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);