d********9
发帖数: 38 | 1 用string形式给一个含有x,y,+,-,*,/,(, )以及double型数字的表达式，比如：
y = (2*x) + 3
要求写一个程序输出x的表达式: x = (y-3)/2;
其中x可能出现多次，比如：y = (x+5)/3 + x*4;
PS: 限制是y是linear in terms of x;
面试当时想的是先简化表达式，将所有含x的terms合并，然后parse这个string生成一
个以y为root的eval tree，然后找到x所在的node，将这个eval tree改造成以这个node
为root的eval tree，然后重建表达式，这样结果就会是x=ay-b之类的形式，不过
interviewer当时
不置可否，我当时也没写出来具体code，求大家帮忙看看有没有什么简明的解法。谢了。 |
r*******g
发帖数: 1335 | 2 感觉很难啊，eval tree中不止一个x啊，怎么用y表示x呢？你说的是reverse polish
expression转化成的eval tree吗(lintcode题目)？ |
d********9
发帖数: 38 | 3 我感觉生成eval tree这一步很简单，我是stuck在如何找到x的表达式这一步...感觉没
有啥好思路
【在 r*******g 的大作中提到】
: 感觉很难啊，eval tree中不止一个x啊，怎么用y表示x呢？你说的是reverse polish
: expression转化成的eval tree吗(lintcode题目)？
|
d********9
发帖数: 38 | |
t*********r
发帖数: 387 | 5 此题无解
y = x*x
提供的符号不能足够表达 |
d********9
发帖数: 38 | 6 哦这个... 暂时只考虑线性情况。
【在 t*********r 的大作中提到】
: 此题无解
: y = x*x
: 提供的符号不能足够表达
|
r*******y
发帖数: 270 | 7 我觉得你考虑的太复杂了，你可以取一些sample input然后看output是多少。根据
input output你就可以算出斜率和截距 同样x y反过来一样 直接出结果 |
t*********r
发帖数: 387 | 8 只有线性不是trivial么？简化成 y = ax + b之后直接转换
【在 d********9 的大作中提到】
: 哦这个... 暂时只考虑线性情况。
|
t*********r
发帖数: 387 | 9 哎这个解法好
【在 r*******y 的大作中提到】
: 我觉得你考虑的太复杂了，你可以取一些sample input然后看output是多少。根据
: input output你就可以算出斜率和截距 同样x y反过来一样 直接出结果
|
d********9
发帖数: 38 | 10 这个我觉得他的用意不是要evaluate这个表达式，而是要求编程实现symbolic
computation.我也不确定我理解的是否正确......
【在 r*******y 的大作中提到】
: 我觉得你考虑的太复杂了，你可以取一些sample input然后看output是多少。根据
: input output你就可以算出斜率和截距 同样x y反过来一样 直接出结果
|
|
|
d********9
发帖数: 38 | 11 我更新了下原帖：
面试当时想的是先简化表达式，将所有含x的terms合并，然后parse这个string生成一
个以y为root的eval tree，然后找到x所在的node，将这个eval tree改造成以这个node
为root的eval tree，然后重建表达式，这样结果就会是x=ay-b之类的形式，不过
interviewer当时
不置可否，我当时也没写出来具体code，求大家帮忙看看有没有什么简明的解法。 |
d********9
发帖数: 38 | |
c******w
发帖数: 1108 | 13 把每个node改一下格式用一对数（a，b）表示ax+b
每evaluate一个四则运算就是算a和b。
node
【在 d********9 的大作中提到】
: 我更新了下原帖：
: 面试当时想的是先简化表达式，将所有含x的terms合并，然后parse这个string生成一
: 个以y为root的eval tree，然后找到x所在的node，将这个eval tree改造成以这个node
: 为root的eval tree，然后重建表达式，这样结果就会是x=ay-b之类的形式，不过
: interviewer当时
: 不置可否，我当时也没写出来具体code，求大家帮忙看看有没有什么简明的解法。
|
c*****m
发帖数: 271 | 14 这个方法蛮好的，但是就算给sample input算output是多少，也不简单啊
【在 r*******y 的大作中提到】
: 我觉得你考虑的太复杂了，你可以取一些sample input然后看output是多少。根据
: input output你就可以算出斜率和截距 同样x y反过来一样 直接出结果
|
j******o
发帖数: 4219 | 15 同意这个，感觉就是让你简化成这个方程式。
【在 t*********r 的大作中提到】
: 只有线性不是trivial么？简化成 y = ax + b之后直接转换
|
r*******y
发帖数: 270 | 16 这不是leetcode原题吗？
【在 c*****m 的大作中提到】
: 这个方法蛮好的，但是就算给sample input算output是多少，也不简单啊
|
r*******g
发帖数: 1335 | 17 如果已经把含有x的terms合并，为何还需要生成eval tree？？
eval tree里面本身会包含多个x
node
【在 d********9 的大作中提到】
: 我更新了下原帖：
: 面试当时想的是先简化表达式，将所有含x的terms合并，然后parse这个string生成一
: 个以y为root的eval tree，然后找到x所在的node，将这个eval tree改造成以这个node
: 为root的eval tree，然后重建表达式，这样结果就会是x=ay-b之类的形式，不过
: interviewer当时
: 不置可否，我当时也没写出来具体code，求大家帮忙看看有没有什么简明的解法。
|
