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

[kingfighters]

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

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

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

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

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

[linfx7]

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

[b821025551b]

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

[bxb100]

一楼正解

[littlepanzh]

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

[lcdtyph]

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

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

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

[cnilnhf]

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

[gamexg]

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

[nbndco]

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

[SpringHack]

1. 逆波兰式
2. x2

[iyaozhen]

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

[kingfighters]

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

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

[acumen]

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

[AccIdent]

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

[chiu]

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

[Cbdy]

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

[kkzxak47]

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

[mayne95]

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

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

[xielemon]

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

[lalalanet]

第二个问题，很简单

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

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

[billion]

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

[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]

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

[syv2]

[syv2]

贴图失败 = =，再试一次

[ybh37]

第一题，在实际应用场景下，我倾向于使用二叉树解决，虽然我也知道栈更简单
实际的表达式计算中常常包含单目、多目、括号等，还有可能混杂常数等情况
[ipad 下某计算器的原作者]

就本题而言，用栈

[tao25]

强力推荐《剑指 offer 》，笔试面试基本不用愁

[ryd994]

第一题其实用树也不错吧，反正把语法树拉出来一看就明了了

[kingfighters]

经过一年多的学习，leetcode 也刷了三百多道题目，再看看这个问题，感觉当时实在是太弱鸡了。。

谢谢楼上的诸位！