j**********3
发帖数: 3211 | 1 如果表达式里有variable，比如有个x，要怎么做？
1 + b + 2 = b + 3
或者 （x ＋ 1）＊ 3 ＋ 2 *（2x + 5） 化简成7x + 13
怎么做？
求个java code |
t********e
发帖数: 344 | |
j**********3
发帖数: 3211 | 3 我也是在别人面经里看到的。。
【在 t********e 的大作中提到】
: 原题是什么？
|
p****e
发帖数: 3548 | |
s**x
发帖数: 7506 | 5 考这个有点过份吧？没有variable 的还差不多。 |
j**********3
发帖数: 3211 | 6 前几天的面经里有个1+b+2 化简成b+3，这个怎么做？
【在 s**x 的大作中提到】
: 考这个有点过份吧？没有variable 的还差不多。
|
p*****3
发帖数: 488 | 7
原本只有 ＋ － ＝ 和 （）。
可以先列出grammar rule, 做递归下降语法分析
res => f = f' => f - f'
f => unit [+/- unit]*
unit => [0-9]*x || [0-9]* || (f)
unit/f/res 均返回 res[x val, num] 比如 res[3, 4] ==> 3x + 4
上面列的3条每个写成一个对应的函数，res为主函数
【在 j**********3 的大作中提到】
: 前几天的面经里有个1+b+2 化简成b+3，这个怎么做？
|
j**********3
发帖数: 3211 | 8 没看懂。。。。。
【在 p*****3 的大作中提到】
:
: 原本只有 ＋ － ＝ 和 （）。
: 可以先列出grammar rule, 做递归下降语法分析
: res => f = f' => f - f'
: f => unit [+/- unit]*
: unit => [0-9]*x || [0-9]* || (f)
: unit/f/res 均返回 res[x val, num] 比如 res[3, 4] ==> 3x + 4
: 上面列的3条每个写成一个对应的函数，res为主函数
|
|
A*****i
发帖数: 3587 | 9 800题大牛是闹着玩的么，这么轻易让你看懂人家800题白做了
【在 j**********3 的大作中提到】
: 没看懂。。。。。
|
j**********3
发帖数: 3211 | 10 你来讲解一下。
【在 A*****i 的大作中提到】
: 800题大牛是闹着玩的么，这么轻易让你看懂人家800题白做了
|
|
|
h*******t
发帖数: 2679 | 11 他的思路灰常厉害。
比如这个：
（x ＋ 1）＊ 3 ＋ 2 *（2x + 5)
这个式子等于：
res[1,1]*res[0,3]+res[0,2]*res[2,5]
只需要对override class res的operator+-*就行了。
当然,grammar parse是少不了的。
【在 j**********3 的大作中提到】
: 你来讲解一下。
|
j**********3
发帖数: 3211 | 12 我大概看明白了你的意思。。。
好像明白了。。。
【在 h*******t 的大作中提到】
: 他的思路灰常厉害。
: 比如这个：
: （x ＋ 1）＊ 3 ＋ 2 *（2x + 5)
: 这个式子等于：
: res[1,1]*res[0,3]+res[0,2]*res[2,5]
: 只需要对override class res的operator+-*就行了。
: 当然,grammar parse是少不了的。
|
h*******t
发帖数: 2679 | 13 多写几个字：
res[a,b]=res[1,1]*res[0,3]+res[0,2]*res[2,5]
要求得到a=7;b=13
>>> 1+b+1 = b+2
相当于
res[a,b] = res[0,1] + res[1,1]
=> a=1,b=2;
【在 j**********3 的大作中提到】
: 我大概看明白了你的意思。。。
: 好像明白了。。。
|
p*****3
发帖数: 488 | 14
好聪明. 来嘴一个。。。 (╯3╰)
【在 h*******t 的大作中提到】
: 多写几个字：
: res[a,b]=res[1,1]*res[0,3]+res[0,2]*res[2,5]
: 要求得到a=7;b=13
: >>> 1+b+1 = b+2
: 相当于
: res[a,b] = res[0,1] + res[1,1]
: => a=1,b=2;
|
s******6
发帖数: 57 | 15
懂了，赞。。。orz
【在 h*******t 的大作中提到】
: 多写几个字：
: res[a,b]=res[1,1]*res[0,3]+res[0,2]*res[2,5]
: 要求得到a=7;b=13
: >>> 1+b+1 = b+2
: 相当于
: res[a,b] = res[0,1] + res[1,1]
: => a=1,b=2;
|
s********l
发帖数: 998 | 16 hahaha~
第一次看到 男生之间这么亲热啊~~
【在 p*****3 的大作中提到】
:
: 好聪明. 来嘴一个。。。 (╯3╰)
|
u*****o
发帖数: 1224 | |
e*******i
发帖数: 56 | 18 parser 菜鸟， anyone can post good code. thanks |
e*******i
发帖数: 56 | 19 哪个大牛发code? Including tokenizer, the total lines of code would be around
100? |
h*******l
发帖数: 9 | 20 三个函数没看懂啊，举例讲讲？
【在 p*****3 的大作中提到】
:
: 好聪明. 来嘴一个。。。 (╯3╰)
|
|
|
f*******w
发帖数: 1243 | 21
赞
不过如果多变量怎么办？
而且parser好像很难写的样子
【在 p*****3 的大作中提到】
:
: 好聪明. 来嘴一个。。。 (╯3╰)
|
j**********3
发帖数: 3211 | 22 如果表达式里有variable，比如有个x，要怎么做？
1 + b + 2 = b + 3
或者 （x ＋ 1）＊ 3 ＋ 2 *（2x + 5） 化简成7x + 13
怎么做？
求个java code |
t********e
发帖数: 344 | |
j**********3
发帖数: 3211 | 24 我也是在别人面经里看到的。。
【在 t********e 的大作中提到】
: 原题是什么？
|
p****e
发帖数: 3548 | |
s**x
发帖数: 7506 | 26 考这个有点过份吧？没有variable 的还差不多。 |
j**********3
发帖数: 3211 | 27 前几天的面经里有个1+b+2 化简成b+3，这个怎么做？
【在 s**x 的大作中提到】
: 考这个有点过份吧？没有variable 的还差不多。
|
p*****3
发帖数: 488 | 28
原本只有 ＋ － ＝ 和 （）。
可以先列出grammar rule, 做递归下降语法分析
res => f = f' => f - f'
f => unit [+/- unit]*
unit => [0-9]*x || [0-9]* || (f)
unit/f/res 均返回 res[x val, num] 比如 res[3, 4] ==> 3x + 4
上面列的3条每个写成一个对应的函数，res为主函数
【在 j**********3 的大作中提到】
: 前几天的面经里有个1+b+2 化简成b+3，这个怎么做？
|
j**********3
发帖数: 3211 | 29 没看懂。。。。。
【在 p*****3 的大作中提到】
:
: 原本只有 ＋ － ＝ 和 （）。
: 可以先列出grammar rule, 做递归下降语法分析
: res => f = f' => f - f'
: f => unit [+/- unit]*
: unit => [0-9]*x || [0-9]* || (f)
: unit/f/res 均返回 res[x val, num] 比如 res[3, 4] ==> 3x + 4
: 上面列的3条每个写成一个对应的函数，res为主函数
|
A*****i
发帖数: 3587 | 30 800题大牛是闹着玩的么，这么轻易让你看懂人家800题白做了
【在 j**********3 的大作中提到】
: 没看懂。。。。。
|
|
|
j**********3
发帖数: 3211 | 31 你来讲解一下。
【在 A*****i 的大作中提到】
: 800题大牛是闹着玩的么，这么轻易让你看懂人家800题白做了
|
h*******t
发帖数: 2679 | 32 他的思路灰常厉害。
比如这个：
（x ＋ 1）＊ 3 ＋ 2 *（2x + 5)
这个式子等于：
res[1,1]*res[0,3]+res[0,2]*res[2,5]
只需要对override class res的operator+-*就行了。
当然,grammar parse是少不了的。
【在 j**********3 的大作中提到】
: 你来讲解一下。
|
j**********3
发帖数: 3211 | 33 我大概看明白了你的意思。。。
好像明白了。。。
【在 h*******t 的大作中提到】
: 他的思路灰常厉害。
: 比如这个：
: （x ＋ 1）＊ 3 ＋ 2 *（2x + 5)
: 这个式子等于：
: res[1,1]*res[0,3]+res[0,2]*res[2,5]
: 只需要对override class res的operator+-*就行了。
: 当然,grammar parse是少不了的。
|
h*******t
发帖数: 2679 | 34 多写几个字：
res[a,b]=res[1,1]*res[0,3]+res[0,2]*res[2,5]
要求得到a=7;b=13
>>> 1+b+1 = b+2
相当于
res[a,b] = res[0,1] + res[1,1]
=> a=1,b=2;
【在 j**********3 的大作中提到】
: 我大概看明白了你的意思。。。
: 好像明白了。。。
|
p*****3
发帖数: 488 | 35
好聪明. 来嘴一个。。。 (╯3╰)
【在 h*******t 的大作中提到】
: 多写几个字：
: res[a,b]=res[1,1]*res[0,3]+res[0,2]*res[2,5]
: 要求得到a=7;b=13
: >>> 1+b+1 = b+2
: 相当于
: res[a,b] = res[0,1] + res[1,1]
: => a=1,b=2;
|
s******6
发帖数: 57 | 36
懂了，赞。。。orz
【在 h*******t 的大作中提到】
: 多写几个字：
: res[a,b]=res[1,1]*res[0,3]+res[0,2]*res[2,5]
: 要求得到a=7;b=13
: >>> 1+b+1 = b+2
: 相当于
: res[a,b] = res[0,1] + res[1,1]
: => a=1,b=2;
|
s********l
发帖数: 998 | 37 hahaha~
第一次看到 男生之间这么亲热啊~~
【在 p*****3 的大作中提到】
:
: 好聪明. 来嘴一个。。。 (╯3╰)
|
u*****o
发帖数: 1224 | |
e*******i
发帖数: 56 | 39 parser 菜鸟， anyone can post good code. thanks |
e*******i
发帖数: 56 | 40 哪个大牛发code? Including tokenizer, the total lines of code would be around
100? |
|
|
h*******l
发帖数: 9 | 41 三个函数没看懂啊，举例讲讲？
【在 p*****3 的大作中提到】
:
: 好聪明. 来嘴一个。。。 (╯3╰)
|
f*******w
发帖数: 1243 | 42
赞
不过如果多变量怎么办？
而且parser好像很难写的样子
【在 p*****3 的大作中提到】
:
: 好聪明. 来嘴一个。。。 (╯3╰)
|
f**********t
发帖数: 1001 | 43 Well, my code is complex and sigfault. Let me go back if I have time.
This is too hard for a 45 minutes interview.
void skipSpace(const char **s) {
while (isspace(**s)) {
++(*s);
}
}
int getNum(const char **s) {
bool neg = false;
if (**s == '-') {
neg = true;
++(*s);
}
int cur = 0;
while (isdigit(**s)) {
cur = cur * 10 + (**s - '0');
++(*s);
}
--(*s);
return neg ? -cur : cur;
}
int opNum(int x, int y, char op) {
switch (op) {
case '+':
return x + y;
case '_':
return x - y;
case '*':
return x * y;
case '/':
if (y == 0) {
return 0;
}
return x / y;
}
return 0;
}
int calc(stack &ops, stack &nums) {
int x = nums.top();
nums.pop();
int y = nums.top();
nums.pop();
int res = opNum(x, y, ops.top());
ops.pop();
nums.push(res);
return res;
}
string calculate(const char *str) {
const char *s = str;
skipSpace(&s);
stack ops;
stack nums;
map vals;
bool afterVal = false;
char whichVal;
bool neg = false;
while (*s) {
if (*s == '(') {
ops.push(*s);
} else if (*s == ')') {
while (ops.top() != '(') {
calc(ops, nums);
}
ops.pop();
} else if (*s == '/' || *s == '*') {
while (!ops.empty() && (ops.top() == '/' || ops.top() == '*')) {
calc(ops, nums);
}
ops.push(*s);
} else if (*s == '+' || *s == '-') {
while (!ops.empty() && ops.top() != '(') {
calc(ops, nums);
}
if (afterVal) {
neg = *s == '-' ? true : false;
} else {
ops.push(*s);
}
} else if (!isdigit(*s) && *s != '-') {
afterVal = true;
whichVal = *s;
if (str < s && !isdigit(*(s - 1))) { // 1 + 1 * 2x + 2 * x
nums.push(1);
}
while (!ops.empty() && (ops.top() == '/' || ops.top() == '*')) {
calc(ops, nums);
}
int coefficient = 1;
if (!nums.empty()) {
coefficient = nums.top();
nums.pop();
}
if (!ops.empty()) {
if (ops.top() == '-') {
coefficient = -coefficient;
}
ops.pop();
}
vals[*s] += coefficient;
} else {
int cur = getNum(&s);
cur = neg ? -cur : cur;
nums.push(cur);
}
++s;
skipSpace(&s);
}
while (!ops.empty()) {
calc(ops, nums);
}
int b = nums.empty() ? 0 : nums.top();
char buf[1024];
int idx = 0;
for (auto x : vals) {
if (x.second != 0) {
int n = sprintf(buf + idx, "%d%cr + ", x.second, x.first);
idx += n;
}
}
if (b == 0) {
if (idx > 3) {
idx -= 3;
}
} else {
int n = sprintf(buf + idx, "%d", b);
idx += n;
}
return string(buf, buf + idx);
}
int main() {
cout << calculate("(10x + 3 *2 ) * 2") << ' '
<< calculate("01 + 3x + 2* 2 ") << ' '
<< calculate("(1+3 ) *2x ") << endl;
return 0;
} |
j**********g
发帖数: 77 | |
t******5
发帖数: 30 | |
S*******C
发帖数: 822 | |
S********0
发帖数: 5749 | 47 也贴个自己的code， 跟前面一个童鞋说的类似，碰见扩号或者等号就递归，这样子也
很容易扩展到乘号或者除号.
double solve(string str, double x) {
int x_coeff, y_coeff, con;
int size = str.size();
x_coeff = y_coeff = con = 0;
getCoeff(str, 0, x_coeff, y_coeff, con);
if (y_coeff != 0) {
double y = -(con + x_coeff*x) / y_coeff;
return y;
}
else return DBL_MAX;
}
int getCoeff(string &str, int start, int &x_coeff, int &y_coeff, int &con) {
int end;
int num;
int digit_flag = 0;
int sign = 1;
int i;
for (i = start; i < str.size(); i++) {
num = 0;
if (str[i] == ' ') continue;
while (str[i] >= '0' && str[i] <= '9') {
num = num * 10 + str[i] - '0';
i++;
digit_flag = 1;
}
if (digit_flag == 1) {
if (str[i] == 'x') x_coeff += sign * num;
else if (str[i] == 'y') y_coeff += sign * num;
else con += sign * num;
digit_flag = 0;
}
else {
if (str[i] == 'x') x_coeff += sign;
else if (str[i] == 'y') y_coeff += sign;
}
if (str[i] == '+') sign = 1;
else if (str[i] == '-') sign = -1;
if (str[i] == '(') {
int a, b, c;
a = b = c = 0;
i = getCoeff(str, i+1, a, b, c);
x_coeff += sign * a;
y_coeff += sign * b;
con += sign * c;
}
else if (str[i] == '=') {
int a, b, c;
a = b = c = 0;
i = getCoeff(str, i + 1, a, b, c);
x_coeff -= a;
y_coeff -= b;
con -= c;
}
else if (str[i] == ')') return i;
}
return i;
} |
g**s
发帖数: 2331 | 48 写的好快
【在 S********0 的大作中提到】
: 也贴个自己的code， 跟前面一个童鞋说的类似，碰见扩号或者等号就递归，这样子也
: 很容易扩展到乘号或者除号.
: double solve(string str, double x) {
: int x_coeff, y_coeff, con;
: int size = str.size();
: x_coeff = y_coeff = con = 0;
:
: getCoeff(str, 0, x_coeff, y_coeff, con);
: if (y_coeff != 0) {
: double y = -(con + x_coeff*x) / y_coeff;
|
j**********g
发帖数: 77 | |
S********0
发帖数: 5749 | 50 没有没有，之前准备fb时候写的
【在 g**s 的大作中提到】
: 写的好快
|
|
|
g**s
发帖数: 2331 | 51 已收藏，明天学习。
【在 S********0 的大作中提到】
: 没有没有，之前准备fb时候写的
|
b*******d
发帖数: 750 | 52 不知道如果按照数值计算那种方法会否得分～？
f(x) = g(x)
---> f(x) - g(x) = 0
知道是x的线性方程，一定收敛， 定个tolerance，binary search。。。 |
r****7
发帖数: 2282 | 53 我感觉这个实现并不容易扩展到乘号或者除号啊
这个题用DS书上经典的postfix expression有什么问题么?
【在 S********0 的大作中提到】
: 也贴个自己的code， 跟前面一个童鞋说的类似，碰见扩号或者等号就递归，这样子也
: 很容易扩展到乘号或者除号.
: double solve(string str, double x) {
: int x_coeff, y_coeff, con;
: int size = str.size();
: x_coeff = y_coeff = con = 0;
:
: getCoeff(str, 0, x_coeff, y_coeff, con);
: if (y_coeff != 0) {
: double y = -(con + x_coeff*x) / y_coeff;
|
m*****n
发帖数: 2152 | 54 要是 (x+1)*x + x*(2x+5)怎么做？
【在 h*******t 的大作中提到】
: 他的思路灰常厉害。
: 比如这个：
: （x ＋ 1）＊ 3 ＋ 2 *（2x + 5)
: 这个式子等于：
: res[1,1]*res[0,3]+res[0,2]*res[2,5]
: 只需要对override class res的operator+-*就行了。
: 当然,grammar parse是少不了的。
|
r****7
发帖数: 2282 | 55 这个变成2次方程了。。。
不过也可以track，把规则变一下就行了。
我觉得这个题的难度还是在parser上边
【在 m*****n 的大作中提到】
: 要是 (x+1)*x + x*(2x+5)怎么做？
|
T******7
发帖数: 1419 | 56 Niu
★ 发自iPhone App: ChineseWeb 8.7
【在 S********0 的大作中提到】
: 也贴个自己的code， 跟前面一个童鞋说的类似，碰见扩号或者等号就递归，这样子也
: 很容易扩展到乘号或者除号.
: double solve(string str, double x) {
: int x_coeff, y_coeff, con;
: int size = str.size();
: x_coeff = y_coeff = con = 0;
:
: getCoeff(str, 0, x_coeff, y_coeff, con);
: if (y_coeff != 0) {
: double y = -(con + x_coeff*x) / y_coeff;
|
k*********n
发帖数: 6 | |
k*********n
发帖数: 6 | |
