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

[kingfighters]

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

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

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

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

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

[billion]

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

[Allianzcortex]

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

[zhuangzhuang1988]

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

[wy315700]

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

[owt5008137]

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

[q397064399]

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

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

[xielemon]

@Allianzcortex 确实是，我记错了

[wizardoz]

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

[20015jjw]

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

[yeyuexia]

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

[WangYanjie]

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

[hanbing135]

lz 的基础知识面太虚了

[luw2007]

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

[yanzixuan]

@gamexg python 高性能编程倒是有讲到。不是直接翻倍，而是有一个范围。

[staticor]

关于第 1 题可以作为拓展知识了解了解.

https://en.wikipedia.org/wiki/Reverse_Polish_notation

https://www.codewars.com/kata/infix-to-postfix-converter/python

[noNOno]

哈哈，第二题有趣， 1,2.....10...100...
规律递增， 10 进制，每 10 行多存一个字符，由于是大文件词典，实现是会按最大占用分配，每行占 10w 数字字符大小的内存。这个问题在 spark 跑的时候遇到

[noNOno]

@noNOno 矩阵形式

[romanticbao]

第二题，没看懂，意思是说，变长数组是如何实现的？

[lalalanet]

@Allianzcortex 人家说的是数组 数组 数组 。 arraylist 是数组嘛 ，那是 array 实现的 list

一行 java 代码
int[] ary = new int[100000]

[kingfighters]

感谢楼上诸位，见笑了。我的知识面确实不够，需要补习算法和数据结构的知识。