f*7
2 楼
题目一出，我就傻眼了，就知道完蛋了。。。
这题目正好是隔壁BB Onsite面经第二题
给一个表达式，计算返回值，不带括号
例子
"7-12/6"
"1000-5*6/3*2+1"
写了半天，问对方，对吗？ 多方说，你说呢。。。
祝大家好运吧，哪个大牛给个链接
这题目正好是隔壁BB Onsite面经第二题
给一个表达式，计算返回值，不带括号
例子
"7-12/6"
"1000-5*6/3*2+1"
写了半天，问对方，对吗？ 多方说，你说呢。。。
祝大家好运吧，哪个大牛给个链接
c*a
3 楼
成交量为0的飘过。。。
p*2
4 楼
看了一下。这题你怎么做的？
感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
b*j
5 楼
是吗？今天我成交量是礼拜一到礼拜五的总和啊。
【在 g*****i 的大作中提到】
: 成交量低，成交价也低。咳，历史新低啊。
【在 g*****i 的大作中提到】
: 成交量低，成交价也低。咳，历史新低啊。
a*o
6 楼
stack就行了,或者搞个temp variable
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
f*n
7 楼
偶这一两天也是啥客人都没有。
h*0
8 楼
2爷您的想法和我之前onsite BB的想法一样。。 结果面试官压根不屌我。 必须用
recursive。 我说recursive不好，被华丽丽的鄙视了。。。
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
recursive。 我说recursive不好，被华丽丽的鄙视了。。。
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
R*g
9 楼
我也是0
p*2
10 楼
stack更简单吗？
【在 a***o 的大作中提到】
: stack就行了,或者搞个temp variable
l*n
11 楼
套套和情趣用品出外...
看来是接了石头阿姨的班
【在 b**j 的大作中提到】
: 是吗？今天我成交量是礼拜一到礼拜五的总和啊。
看来是接了石头阿姨的班
【在 b**j 的大作中提到】
: 是吗？今天我成交量是礼拜一到礼拜五的总和啊。
p*2
12 楼
recursive怎么搞呀？
【在 h*******0 的大作中提到】
: 2爷您的想法和我之前onsite BB的想法一样。。 结果面试官压根不屌我。 必须用
: recursive。 我说recursive不好，被华丽丽的鄙视了。。。
b*j
13 楼
明天就情人节了今天order，礼拜六，明天怎么deliver啊。呵呵
【在 l******n 的大作中提到】
: 套套和情趣用品出外...
: 看来是接了石头阿姨的班
【在 l******n 的大作中提到】
: 套套和情趣用品出外...
: 看来是接了石头阿姨的班
f*7
14 楼
二爷这题我没见过，硬着头皮写recursive，思路都不对，今天就问了这一题。。。
有相关讲解的链接吗？
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
有相关讲解的链接吗？
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
l*n
15 楼
都是overnight呀
BSO shipping都赚疯了
【在 b**j 的大作中提到】
: 明天就情人节了今天order，礼拜六，明天怎么deliver啊。呵呵
BSO shipping都赚疯了
【在 b**j 的大作中提到】
: 明天就情人节了今天order，礼拜六，明天怎么deliver啊。呵呵
h*0
16 楼
我当时也没想出来。 然后我和他说，我这个方法比recursive好。。 我说recursive可
能会out of memory。 人家根本不同意我的说法。
【在 p*****2 的大作中提到】
:
: recursive怎么搞呀？
能会out of memory。 人家根本不同意我的说法。
【在 p*****2 的大作中提到】
:
: recursive怎么搞呀？
h*0
17 楼
我觉得如果见到没见过的题就要赶紧研究。。 弄不好就是你下一道题。。 这题其实挺
不好写的
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
不好写的
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
p*2
18 楼
我大概的想法
1000-5*6/3*2+1
用个双向链表
1000 - 5 * 6 / 3 * 2 + 1
第一遍算乘除， 比如 看到第一个 ＊ 就把prev * next 然后把5*6拿掉，把结果30放
进去，就成了
1000 - 30 / 3 * 2 + 1
第二遍算加减就从头算到尾就可以了
想想有没有什么更简单的办法。
【在 f*******7 的大作中提到】
: 二爷这题我没见过，硬着头皮写recursive，思路都不对，今天就问了这一题。。。
: 有相关讲解的链接吗？
a*o
19 楼
搞俩variable就行了,一个存之前的数,
一个存当前的数,碰到乘除,更新当前的数,碰到加减更新之前的数
【在 p*****2 的大作中提到】
:
: 我大概的想法
: 1000-5*6/3*2+1
: 用个双向链表
: 1000 - 5 * 6 / 3 * 2 + 1
: 第一遍算乘除， 比如 看到第一个 ＊ 就把prev * next 然后把5*6拿掉，把结果30放
: 进去，就成了
: 1000 - 30 / 3 * 2 + 1
: 第二遍算加减就从头算到尾就可以了
: 想想有没有什么更简单的办法。
一个存当前的数,碰到乘除,更新当前的数,碰到加减更新之前的数
【在 p*****2 的大作中提到】
:
: 我大概的想法
: 1000-5*6/3*2+1
: 用个双向链表
: 1000 - 5 * 6 / 3 * 2 + 1
: 第一遍算乘除， 比如 看到第一个 ＊ 就把prev * next 然后把5*6拿掉，把结果30放
: 进去，就成了
: 1000 - 30 / 3 * 2 + 1
: 第二遍算加减就从头算到尾就可以了
: 想想有没有什么更简单的办法。
p*e
20 楼
搞了个复杂的。。
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from
stdin).
#include
using namespace std;
bool OpHigherOrder(char c1, char c2)
{
if(c1 != '(' && c2 == ')')
return true;
else if(c1 == '(')
return false;
else if((c1 == '*' || c1 == '/'))
return true;
else if((c1 == '+' || c1 == '-') && (c2 == '+' || c2 == '-'))
return true;
else
return false;
}
double CalOp(double e1, char op, double e2)
{
switch(op)
{
case '+':
return e1 + e2;
case '-':
return e1 - e2;
case '*':
return e1 * e2;
case '/':
return e1 / e2;
}
}
double CalExpression(string a)
{
stack num;
stack op;
int numpos = 0;
for(int i = 0; i < a.length(); i++)
{
if(a[i] == ' ')
{
a.erase(i, 1);
i--;
continue;
}
if((a[i]>='0' && a[i]<='9') || a[i] == '.')
{
continue;
}
if(a[i] == '(')
{
op.push('(');
numpos = i + 1;
continue;
}
if(numpos < i)
{
num.push(atof(a.substr(numpos, i - numpos).c_str()));
}
while(op.size() > 0 && num.size()>1)
{
if(OpHigherOrder(op.top(), a[i]))
{
double right = num.top();
num.pop();
double left = num.top();
num.pop();
num.push(CalOp(left, op.top(), right));
op.pop();
}
else
{
break;
}
}
if(a[i] == ')')
{
op.pop();
}
else
op.push(a[i]);
numpos = i + 1;
}
if(numpos < a.length())
num.push(atof(a.substr(numpos).c_str()));
while(op.size() > 0 && num.size()>1)
{
double right = num.top();
num.pop();
double left = num.top();
num.pop();
num.push(CalOp(left, op.top(), right));
op.pop();
}
return num.top();
}
int main() {
// Start typing your code here...
string s("12+5*62/2-3*(5+3*(5+6))");
cout << CalExpression(s) << endl;
return 0;
}
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from
stdin).
#include
using namespace std;
bool OpHigherOrder(char c1, char c2)
{
if(c1 != '(' && c2 == ')')
return true;
else if(c1 == '(')
return false;
else if((c1 == '*' || c1 == '/'))
return true;
else if((c1 == '+' || c1 == '-') && (c2 == '+' || c2 == '-'))
return true;
else
return false;
}
double CalOp(double e1, char op, double e2)
{
switch(op)
{
case '+':
return e1 + e2;
case '-':
return e1 - e2;
case '*':
return e1 * e2;
case '/':
return e1 / e2;
}
}
double CalExpression(string a)
{
stack
stack
int numpos = 0;
for(int i = 0; i < a.length(); i++)
{
if(a[i] == ' ')
{
a.erase(i, 1);
i--;
continue;
}
if((a[i]>='0' && a[i]<='9') || a[i] == '.')
{
continue;
}
if(a[i] == '(')
{
op.push('(');
numpos = i + 1;
continue;
}
if(numpos < i)
{
num.push(atof(a.substr(numpos, i - numpos).c_str()));
}
while(op.size() > 0 && num.size()>1)
{
if(OpHigherOrder(op.top(), a[i]))
{
double right = num.top();
num.pop();
double left = num.top();
num.pop();
num.push(CalOp(left, op.top(), right));
op.pop();
}
else
{
break;
}
}
if(a[i] == ')')
{
op.pop();
}
else
op.push(a[i]);
numpos = i + 1;
}
if(numpos < a.length())
num.push(atof(a.substr(numpos).c_str()));
while(op.size() > 0 && num.size()>1)
{
double right = num.top();
num.pop();
double left = num.top();
num.pop();
num.push(CalOp(left, op.top(), right));
op.pop();
}
return num.top();
}
int main() {
// Start typing your code here...
string s("12+5*62/2-3*(5+3*(5+6))");
cout << CalExpression(s) << endl;
return 0;
}
p*2
21 楼
1000-5*6/3*2+1
recursion的话
1000 － 然后往后找到 ＋， － 或者end
变成
1000- f(5*6/3*2) + 1
主要是纪录＋－的位置。比如上边的例子，4 13
然后分段算 f(0,3) - f(5, 12) + f(14)
recursion的话
1000 － 然后往后找到 ＋， － 或者end
变成
1000- f(5*6/3*2) + 1
主要是纪录＋－的位置。比如上边的例子，4 13
然后分段算 f(0,3) - f(5, 12) + f(14)
h*8
22 楼
尝试构造一个对应的AST？不知道可不可以
p*2
23 楼
应该可以。就是写起来不知道是不是容易bug free。你可以写写看看。
【在 a***o 的大作中提到】
: 搞俩variable就行了,一个存之前的数,
: 一个存当前的数,碰到乘除,更新当前的数,碰到加减更新之前的数
o*d
24 楼
我记得这个是我在国内尚数据结构时stack的李子(当然可能各个学校不一样),参考严蔚
敏的书
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
敏的书
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
o*d
25 楼
另外,这个我在careercup上见过google也考过似乎
【在 o***d 的大作中提到】
: 我记得这个是我在国内尚数据结构时stack的李子(当然可能各个学校不一样),参考严蔚
: 敏的书
【在 o***d 的大作中提到】
: 我记得这个是我在国内尚数据结构时stack的李子(当然可能各个学校不一样),参考严蔚
: 敏的书
b*u
26 楼
试着写了一个递归的
思路： 每个recursion的开始有一个factor，一个当前operand和一个之前乘/除号
首先把operand = operand 乘除 factor
然后，如果下一符号是加减，则返回 operand 加减下一recursion（factor=1， 乘）
如果下一符号是乘除，则返回下一recursion (factor=当前operand, 下一符号）
(on a second thought, 这个其实也就是实现了一个stack的功能，递归即stack)
#include "stdafx.h"
#include
#include
#include
using namespace std;
int stringCalculator(string input, int factor, char sign)
{
int len = input.length();
if (len == 0) return 0;
int i = 0;
while (i< len && input[i]>='0' && input[i]<='9')
{
++i;
}
int rightEnd = min (len, i);
int operand = atoi(input.substr(0,rightEnd).c_str());
if (sign == '*')
operand *= factor;
else
operand /= factor;
if (i == len)
return operand;
else
{
switch (input[i])
{
case '+':
return operand+stringCalculator(input.substr(i+1), 1, '*');
case '-':
return operand-stringCalculator(input.substr(i+1), 1, '*');
default:
return stringCalculator(input.substr(i+1), operand, input[i]);
break;
}
}
}
int calculator (string input)
{
return stringCalculator(input,1,'*');
}
int _tmain(int argc, _TCHAR* argv[])
{
string test = "1+2*3";
cout << calculator (test);
cin.get();
return 0;
}
思路： 每个recursion的开始有一个factor，一个当前operand和一个之前乘/除号
首先把operand = operand 乘除 factor
然后，如果下一符号是加减，则返回 operand 加减下一recursion（factor=1， 乘）
如果下一符号是乘除，则返回下一recursion (factor=当前operand, 下一符号）
(on a second thought, 这个其实也就是实现了一个stack的功能，递归即stack)
#include "stdafx.h"
#include
#include
#include
using namespace std;
int stringCalculator(string input, int factor, char sign)
{
int len = input.length();
if (len == 0) return 0;
int i = 0;
while (i< len && input[i]>='0' && input[i]<='9')
{
++i;
}
int rightEnd = min (len, i);
int operand = atoi(input.substr(0,rightEnd).c_str());
if (sign == '*')
operand *= factor;
else
operand /= factor;
if (i == len)
return operand;
else
{
switch (input[i])
{
case '+':
return operand+stringCalculator(input.substr(i+1), 1, '*');
case '-':
return operand-stringCalculator(input.substr(i+1), 1, '*');
default:
return stringCalculator(input.substr(i+1), operand, input[i]);
break;
}
}
}
int calculator (string input)
{
return stringCalculator(input,1,'*');
}
int _tmain(int argc, _TCHAR* argv[])
{
string test = "1+2*3";
cout << calculator (test);
cin.get();
return 0;
}
m*1
27 楼
电面考这个，要求有点高啊，写计算器是以前学做编译原理搞语法和词法分析的小
project哎
project哎
w*x
28 楼
int mul(const char*& p);
int num(const char*& p);
int Add(const char*& p)
{
int res = mul(p);
while (*p == '+' || *p == '-')
{
if (*p == '+')
res += mul(++p);
else
res -= mul(++p);
}
return res;
}
int mul(const char*& p)
{
int res = num(p);
while (*p == '*' || *p == '/')
{
if (*p == '*')
res *= num(++p);
else
res /= num(++p);
}
return res;
}
int num(const char*& p)
{
bool bNeg = false;
if (*p == '-')
{
bNeg = true;
p++;
}
int res = 0;
while (*p >= '0' && *p <= '9')
res = res*10 + *p++ - '0';
return bNeg ? -res : res;
}
递归下降
Add = mul | (+- mul)*
mul = num | (+- num)*
num = (+-)[0-9]*
int num(const char*& p);
int Add(const char*& p)
{
int res = mul(p);
while (*p == '+' || *p == '-')
{
if (*p == '+')
res += mul(++p);
else
res -= mul(++p);
}
return res;
}
int mul(const char*& p)
{
int res = num(p);
while (*p == '*' || *p == '/')
{
if (*p == '*')
res *= num(++p);
else
res /= num(++p);
}
return res;
}
int num(const char*& p)
{
bool bNeg = false;
if (*p == '-')
{
bNeg = true;
p++;
}
int res = 0;
while (*p >= '0' && *p <= '9')
res = res*10 + *p++ - '0';
return bNeg ? -res : res;
}
递归下降
Add = mul | (+- mul)*
mul = num | (+- num)*
num = (+-)[0-9]*
j*y
29 楼
int value(int a, int b, char c)
{
if(c == '+') return a + b;
if(c == '-') return a - b;
if(c == '*') return a * b;
if(c == '/') return a / b;
}
int expression(vector s)
{
if(s.size() == 0)
{
return 0;
}
stack operand;
stack operator;
operand.push(atoi(s.c_str()));
for(int i = 0; i < input.size(); ++i)
{
if(isnumber(s[i][0]))
{
operand.push(atoi(s[i].c_str()));
}
else
{ char c = s[i][0];
if(c == '*' || c == '/')
{
int a = atoi(s[++i].c_str());
a = value(operand.top(), a, c);
operand.pop();
operand.push(a);
}
else
{
if(operand.size() == 2)
{
int b = operand.top();
operand.pop();
int a = operand.top();
operand.pop();
operand.push(value(a, b, operator.top()));
operator.pop();
}
else
{
operator.push(c);
}
}
}
}
if(operand.size() == 2)
{
int b = operand.top();
operand.pop();
int a = operand.top();
return value(a, b, operator.top());
}
else
{
return operand.top();
}
}
感觉不用 stack也可以， 因为 stack里面只有一个或者两个 item
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
{
if(c == '+') return a + b;
if(c == '-') return a - b;
if(c == '*') return a * b;
if(c == '/') return a / b;
}
int expression(vector
{
if(s.size() == 0)
{
return 0;
}
stack
stack
operand.push(atoi(s.c_str()));
for(int i = 0; i < input.size(); ++i)
{
if(isnumber(s[i][0]))
{
operand.push(atoi(s[i].c_str()));
}
else
{ char c = s[i][0];
if(c == '*' || c == '/')
{
int a = atoi(s[++i].c_str());
a = value(operand.top(), a, c);
operand.pop();
operand.push(a);
}
else
{
if(operand.size() == 2)
{
int b = operand.top();
operand.pop();
int a = operand.top();
operand.pop();
operand.push(value(a, b, operator.top()));
operator.pop();
}
else
{
operator.push(c);
}
}
}
}
if(operand.size() == 2)
{
int b = operand.top();
operand.pop();
int a = operand.top();
return value(a, b, operator.top());
}
else
{
return operand.top();
}
}
感觉不用 stack也可以， 因为 stack里面只有一个或者两个 item
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
p*2
30 楼
def cal(str:String):Int={
val numbers=str.split("[+-/*]").map(_.toInt)
val operators=str.filterNot(_.isDigit)
var result=numbers(0)
for(icase '+' => result+=numbers(i+1)
case '-' => result-=numbers(i+1)
case '*' => result*=numbers(i+1)
case '/' => result/=numbers(i+1)
}
result
}
def solve(str:String):Int={
val plusminus= -1 +: (for(istr(i)=='-') yield i)
var sb=new StringBuilder()
for(isb.append(cal(str.slice(plusminus(i-1)+1,plusminus(i))))
sb.append(str(plusminus(i)))
}
sb.append(cal(str.slice(plusminus.last+1, str.length)))
cal(sb.toString)
}
val numbers=str.split("[+-/*]").map(_.toInt)
val operators=str.filterNot(_.isDigit)
var result=numbers(0)
for(icase '+' => result+=numbers(i+1)
case '-' => result-=numbers(i+1)
case '*' => result*=numbers(i+1)
case '/' => result/=numbers(i+1)
}
result
}
def solve(str:String):Int={
val plusminus= -1 +: (for(istr(i)=='-') yield i)
var sb=new StringBuilder()
for(isb.append(cal(str.slice(plusminus(i-1)+1,plusminus(i))))
sb.append(str(plusminus(i)))
}
sb.append(cal(str.slice(plusminus.last+1, str.length)))
cal(sb.toString)
}
h*0
31 楼
为啥感觉你代码写的这么优美呢？ 难道是排版排的好？ ：）
【在 w****x 的大作中提到】
: int mul(const char*& p);
: int num(const char*& p);
: int Add(const char*& p)
: {
: int res = mul(p);
: while (*p == '+' || *p == '-')
: {
: if (*p == '+')
: res += mul(++p);
: else
【在 w****x 的大作中提到】
: int mul(const char*& p);
: int num(const char*& p);
: int Add(const char*& p)
: {
: int res = mul(p);
: while (*p == '+' || *p == '-')
: {
: if (*p == '+')
: res += mul(++p);
: else
q*s
32 楼
这个不是逆波兰吗？
★ 发自iPhone App: ChineseWeb 7.8
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
★ 发自iPhone App: ChineseWeb 7.8
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
a*o
33 楼
写的漂亮,可能C比较简洁
【在 h*******0 的大作中提到】
: 为啥感觉你代码写的这么优美呢？ 难道是排版排的好？ ：）
【在 h*******0 的大作中提到】
: 为啥感觉你代码写的这么优美呢？ 难道是排版排的好？ ：）
e*e
34 楼
凑个热闹!
public int calculate( String[] in, int sIdx ) {
if ( sIdx == in.length - 1)
return toInt( in[sIdx] );
int addOrMinus = getAddOrMinusSign( in[sIdx + 1] );
if ( addOrMinus != 0 ) {
if ( sIdx + 2 == in.length - 1 || getAddOrMinusSign( in[sIdx + 3] ) !=
0 ) {
in[sIdx+2] = toStr( toInt( in[sIdx] ) + addOrMinus*toInt( in[sIdx+
2] ) );
return calculate( in, sIdx + 2 );
} else {
calMulOrDivAndSetBack( in, sIdx+2 );
in[sIdx+3] = in[sIdx+1];
in[sIdx+2] = in[sIdx];
return calculate( in, sIdx + 2 );
}
}
calMulOrDivAndSetBack( in, sIdx );
return calculate( in, sIdx + 2 );
}
private int getAddOrMinusSign( String s ){
if ( "+".equals( s ) )
return 1;
else if ( "-".equals( s ) )
return -1;
return 0;
}
private void calMulOrDivAndSetBack( String[] in, int idx ) {
if ( "*".equals( in[idx + 1] ) )
in[idx+2] = toStr( toInt( in[idx] ) * toInt( in[idx+2] ) );
else
in[idx+2] = toStr( toInt( in[idx] ) / toInt( in[idx+2] ) );
}
private int toInt( String s ){
return Integer.parseInt( s );
}
private String toStr( Integer i ) {
return Integer.toString( i );
}
public int calculate( String[] in, int sIdx ) {
if ( sIdx == in.length - 1)
return toInt( in[sIdx] );
int addOrMinus = getAddOrMinusSign( in[sIdx + 1] );
if ( addOrMinus != 0 ) {
if ( sIdx + 2 == in.length - 1 || getAddOrMinusSign( in[sIdx + 3] ) !=
0 ) {
in[sIdx+2] = toStr( toInt( in[sIdx] ) + addOrMinus*toInt( in[sIdx+
2] ) );
return calculate( in, sIdx + 2 );
} else {
calMulOrDivAndSetBack( in, sIdx+2 );
in[sIdx+3] = in[sIdx+1];
in[sIdx+2] = in[sIdx];
return calculate( in, sIdx + 2 );
}
}
calMulOrDivAndSetBack( in, sIdx );
return calculate( in, sIdx + 2 );
}
private int getAddOrMinusSign( String s ){
if ( "+".equals( s ) )
return 1;
else if ( "-".equals( s ) )
return -1;
return 0;
}
private void calMulOrDivAndSetBack( String[] in, int idx ) {
if ( "*".equals( in[idx + 1] ) )
in[idx+2] = toStr( toInt( in[idx] ) * toInt( in[idx+2] ) );
else
in[idx+2] = toStr( toInt( in[idx] ) / toInt( in[idx+2] ) );
}
private int toInt( String s ){
return Integer.parseInt( s );
}
private String toStr( Integer i ) {
return Integer.toString( i );
}
w*x
35 楼
可能因为我比较帅吧
【在 h*******0 的大作中提到】
: 为啥感觉你代码写的这么优美呢？ 难道是排版排的好？ ：）
l*a
36 楼
看linkedin不像啊
【在 w****x 的大作中提到】
:
: 可能因为我比较帅吧
【在 w****x 的大作中提到】
:
: 可能因为我比较帅吧
w*x
37 楼
等等，我马上换成刘德华的
【在 l*****a 的大作中提到】
: 看linkedin不像啊
s*s
38 楼
贴个java recursive的吧。
float compute(String exp) {
if(exp == null || exp.length() == 0) return 0;
int plusPos = exp.indexOf('+');
int minusPos = exp.indexOf('-');
if(plusPos < 0 && minusPos < 0) return convert(exp);
if(plusPos < 0 || (minusPos > 0 && minusPos < plusPos))
return convert(exp.substring(0, minusPos)) - compute(exp.
substring(minusPos+1));
if(minusPos < 0 || (plusPos > 0 && plusPos < minusPos))
return convert(exp.substring(0, plusPos)) + compute(exp.
substring(plusPos+1));
return 0;
}
float convert(String exp){
float res = 1;
float curr = 0;
boolean isProduct = true;
for(int i = 0; i < exp.length(); i++){
if(exp.charAt(i) == '*' || exp.charAt(i) == '/'){
if(isProduct)
res = res * curr;
else {
if(curr == 0)
throw new IllegalArgumentException("Denominator is
0");
else res = res/curr;
}
curr = 0;
isProduct = (exp.charAt(i) == '*');
} else {
curr = curr * 10 + (float)(exp.charAt(i) - '0');
}
}
if(isProduct)
res = res * curr;
else {
if(curr == 0)
throw new IllegalArgumentException("Denominator is 0");
else res = res/curr;
}
return res;
}
float compute(String exp) {
if(exp == null || exp.length() == 0) return 0;
int plusPos = exp.indexOf('+');
int minusPos = exp.indexOf('-');
if(plusPos < 0 && minusPos < 0) return convert(exp);
if(plusPos < 0 || (minusPos > 0 && minusPos < plusPos))
return convert(exp.substring(0, minusPos)) - compute(exp.
substring(minusPos+1));
if(minusPos < 0 || (plusPos > 0 && plusPos < minusPos))
return convert(exp.substring(0, plusPos)) + compute(exp.
substring(plusPos+1));
return 0;
}
float convert(String exp){
float res = 1;
float curr = 0;
boolean isProduct = true;
for(int i = 0; i < exp.length(); i++){
if(exp.charAt(i) == '*' || exp.charAt(i) == '/'){
if(isProduct)
res = res * curr;
else {
if(curr == 0)
throw new IllegalArgumentException("Denominator is
0");
else res = res/curr;
}
curr = 0;
isProduct = (exp.charAt(i) == '*');
} else {
curr = curr * 10 + (float)(exp.charAt(i) - '0');
}
}
if(isProduct)
res = res * curr;
else {
if(curr == 0)
throw new IllegalArgumentException("Denominator is 0");
else res = res/curr;
}
return res;
}
x*6
39 楼
先把表达式转换成operand和operator的string[],再转换成postfix notation，最后用
一个stack来帮助计算
一个stack来帮助计算
p*2
40 楼
这个看起来不错。
【在 w****x 的大作中提到】
: int mul(const char*& p);
: int num(const char*& p);
: int Add(const char*& p)
: {
: int res = mul(p);
: while (*p == '+' || *p == '-')
: {
: if (*p == '+')
: res += mul(++p);
: else
s*0
41 楼
向 Edsger Dijkstra 先生致敬：
http://en.wikipedia.org/wiki/Shunting-yard_algorithm
http://en.wikipedia.org/wiki/Shunting-yard_algorithm
l*8
42 楼
double readNumber(const char * &str) {
double num;
sscanf(str, "%lf", &num);
for (++str; isdigit(*str) || *str == '.'; ++str)
;
return num;
}
double calculate(const char * str) {
if (*str == '\0') return 0.0;
double result = 1.0;
char op = '*';
while (op == '*' || op == '/') {
if (op == '*')
result *= readNumber(str);
else
result /= readNumber(str);
op = *str++;
}
return result + calculate(--str);
}
double num;
sscanf(str, "%lf", &num);
for (++str; isdigit(*str) || *str == '.'; ++str)
;
return num;
}
double calculate(const char * str) {
if (*str == '\0') return 0.0;
double result = 1.0;
char op = '*';
while (op == '*' || op == '/') {
if (op == '*')
result *= readNumber(str);
else
result /= readNumber(str);
op = *str++;
}
return result + calculate(--str);
}
l*8
43 楼
测试案例：
-3-4.3+5.05*2/4-4.10/5+3 = -2.595
【在 l*********8 的大作中提到】
: double readNumber(const char * &str) {
: double num;
: sscanf(str, "%lf", &num);
: for (++str; isdigit(*str) || *str == '.'; ++str)
: ;
: return num;
: }
: double calculate(const char * str) {
: if (*str == '\0') return 0.0;
: double result = 1.0;
-3-4.3+5.05*2/4-4.10/5+3 = -2.595
【在 l*********8 的大作中提到】
: double readNumber(const char * &str) {
: double num;
: sscanf(str, "%lf", &num);
: for (++str; isdigit(*str) || *str == '.'; ++str)
: ;
: return num;
: }
: double calculate(const char * str) {
: if (*str == '\0') return 0.0;
: double result = 1.0;
l*b
44 楼
学习了...发愁那个减号怎么处理呢...原来是sscanf...哈哈
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
s*0
45 楼
package myutil;
import java.util.Scanner;
import java.util.Stack;
public class ParseExp {
Stack oprand = new Stack();
Stack oprator = new Stack();
static int[] code = new int[256];
static {
code['+'] = 10;
code['-'] = 11;
code['*'] = 20;
code['/'] = 21;
code['^'] = 30;
code['$'] = 0;
code['('] = 100;
code[')'] = 1;
}
public ParseExp() {
}
public Integer parse(String e) {
Scanner s = new Scanner(e + " $");
oprator.push(-1);
while (true) {
if (s.hasNextInt()) {
oprand.push(s.nextInt());
} else if (s.hasNext("[-$+*/^()]")) {
int optr = code[s.next(".").charAt(0)];
while (!oprator.isEmpty() && oprator.peek() > optr) {
int y = oprand.pop();
int x = oprand.pop();
switch (oprator.pop()) {
case 10:
oprand.push(x + y);
break;
case 11:
oprand.push(x - y);
break;
case 20:
oprand.push(x * y);
break;
case 21:
oprand.push(x * y);
break;
case 30:
oprand.push((int) Math.pow(x, y));
break;
}
}
if (optr == 0)
break;
if (optr == 100) {
oprator.push(1);
continue;
} else if (optr == 1) {
oprator.pop();
continue;
} else
oprator.push(optr);
} else {
System.out.println(s.next());
}
}
return oprand.peek();
}
public static void main(String[] args) {
ParseExp p = new ParseExp();
for (String e : new String[] { "1 + 1", "1 + 2 * 3", "1 * 2 + 3",
"1 + 2 * 3 + 4", "2 ^ 8 + 1 * 4", "1 * 4 + 2 ^ 8 - 4",
"( 2 + 3 ) * ( 4 + 6 ) ^ 2" }) {
System.out.println(e + " = " + p.parse(e));
}
}
}
import java.util.Scanner;
import java.util.Stack;
public class ParseExp {
Stack
Stack
static int[] code = new int[256];
static {
code['+'] = 10;
code['-'] = 11;
code['*'] = 20;
code['/'] = 21;
code['^'] = 30;
code['$'] = 0;
code['('] = 100;
code[')'] = 1;
}
public ParseExp() {
}
public Integer parse(String e) {
Scanner s = new Scanner(e + " $");
oprator.push(-1);
while (true) {
if (s.hasNextInt()) {
oprand.push(s.nextInt());
} else if (s.hasNext("[-$+*/^()]")) {
int optr = code[s.next(".").charAt(0)];
while (!oprator.isEmpty() && oprator.peek() > optr) {
int y = oprand.pop();
int x = oprand.pop();
switch (oprator.pop()) {
case 10:
oprand.push(x + y);
break;
case 11:
oprand.push(x - y);
break;
case 20:
oprand.push(x * y);
break;
case 21:
oprand.push(x * y);
break;
case 30:
oprand.push((int) Math.pow(x, y));
break;
}
}
if (optr == 0)
break;
if (optr == 100) {
oprator.push(1);
continue;
} else if (optr == 1) {
oprator.pop();
continue;
} else
oprator.push(optr);
} else {
System.out.println(s.next());
}
}
return oprand.peek();
}
public static void main(String[] args) {
ParseExp p = new ParseExp();
for (String e : new String[] { "1 + 1", "1 + 2 * 3", "1 * 2 + 3",
"1 + 2 * 3 + 4", "2 ^ 8 + 1 * 4", "1 * 4 + 2 ^ 8 - 4",
"( 2 + 3 ) * ( 4 + 6 ) ^ 2" }) {
System.out.println(e + " = " + p.parse(e));
}
}
}
M*l
46 楼
逆波兰表达式吧？用个stack就行了，两年前面试被问过，当时居然正好复习到了～～
http://baike.baidu.com/view/552648.htm
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
http://baike.baidu.com/view/552648.htm
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
p*2
48 楼
longway又出手了。
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
H*s
49 楼
还是这个牛啊！
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
p*2
50 楼
longway的代码向来都是最简洁的。
【在 H****s 的大作中提到】
: 还是这个牛啊！
e*e
51 楼
写了一个infix to postfix，实现起来简单, 不知道思路还真不好想，面试的时候我肯
定想不出来。逆波兰表达式(postfix)evaluation是常见题，我就不贴了.
public List toPostfix(String[] in) {
List pf = new ArrayList();
Stack stack = new Stack();
for ( String s : in ) {
int p = getPrecedence( s );
if ( p == 0 )
pf.add( s );
else if ( stack.empty() )
stack.push( s );
else {
while( !stack.isEmpty() && getPrecedence( stack.peek() ) >= p )
pf.add( stack.pop() );
stack.push( s );
}
}
while( !stack.isEmpty() )
pf.add( stack.pop() );
return pf;
}
private int getPrecedence(String s) {
switch( s ) {
case "*": return 2;
case "/": return 2;
case "+": return 1;
case "-": return 1;
default : return 0;
}
}
【在 M******l 的大作中提到】
: 逆波兰表达式吧？用个stack就行了，两年前面试被问过，当时居然正好复习到了～～
: http://baike.baidu.com/view/552648.htm
定想不出来。逆波兰表达式(postfix)evaluation是常见题，我就不贴了.
public List
List
Stack
for ( String s : in ) {
int p = getPrecedence( s );
if ( p == 0 )
pf.add( s );
else if ( stack.empty() )
stack.push( s );
else {
while( !stack.isEmpty() && getPrecedence( stack.peek() ) >= p )
pf.add( stack.pop() );
stack.push( s );
}
}
while( !stack.isEmpty() )
pf.add( stack.pop() );
return pf;
}
private int getPrecedence(String s) {
switch( s ) {
case "*": return 2;
case "/": return 2;
case "+": return 1;
case "-": return 1;
default : return 0;
}
}
【在 M******l 的大作中提到】
: 逆波兰表达式吧？用个stack就行了，两年前面试被问过，当时居然正好复习到了～～
: http://baike.baidu.com/view/552648.htm
p*2
52 楼
这东西没搞过。回头看看。
【在 e****e 的大作中提到】
: 写了一个infix to postfix，实现起来简单, 不知道思路还真不好想，面试的时候我肯
: 定想不出来。逆波兰表达式(postfix)evaluation是常见题，我就不贴了.
: public List
: List
: Stack
: for ( String s : in ) {
: int p = getPrecedence( s );
: if ( p == 0 )
: pf.add( s );
: else if ( stack.empty() )
l*8
53 楼
谢谢！ 这道题目， 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
d*f
54 楼
20年前你这么回答可能还行
【在 h*******0 的大作中提到】
: 我当时也没想出来。 然后我和他说，我这个方法比recursive好。。 我说recursive可
: 能会out of memory。 人家根本不同意我的说法。
【在 h*******0 的大作中提到】
: 我当时也没想出来。 然后我和他说，我这个方法比recursive好。。 我说recursive可
: 能会out of memory。 人家根本不同意我的说法。
n*e
55 楼
哈哈，这个牛！居然能这么处理。
【在 l*********8 的大作中提到】
: 谢谢！ 这道题目， 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
: 面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
【在 l*********8 的大作中提到】
: 谢谢！ 这道题目， 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
: 面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
I*s
56 楼
最喜欢 wwwyhx的解法: recursive descent.
我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
#include
#include // for pow()
using namespace std;
struct Node {
double val;
char op;
int op_prec; // precedence of operator
int type; // 0 - operand, 1 - operator
Node * left;
Node * right;
Node(double _val, char _op, int _type) : val(_val), op(_op),
type(_type), left(NULL), right(NULL) {}
};
class Solution {
private:
int prec_base;
const char * p0; // record start position of input string.
void err(char * msg, const char * p) {
printf("input error: %s, at input position %d\n", msg, p - p0);
printf("%s\n", p0);
for (int i = 0, len = p - p0; i < len; ++ i) putchar(' ');
printf("^\n");
exit(1);
}
void dump_node(Node * n) {
if (n->type == 0) printf(" %.1lf ", n->val);
else printf(" %c ", n->op);
}
void dump(Node * n) {
if (! n) return;
if (! n->left && ! n->right) {
dump_node(n);
return;
}
printf("(");
dump(n->left);
dump_node(n);
dump(n->right);
printf(")");
}
int prec(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
if (op == '^') return 3;
return 0;
}
int isOp(char c) {
return (c == '+' || c == '-' || c == '*' ||
c == '/' || c == '^');
}
int isDigit(char c) { return c >= '0' && c <= '9'; }
// type - desired type of new token. 0 - operand, 1 - operator.
Node * getNextToken(const char *& input, int type) {
const int prec_base_inc = 4; // 1 + max(op prec)
while (isspace(*input)) ++ input; // skips spaces.
if (! *input) return NULL; // end of input.
while (*input == '(') {
prec_base += prec_base_inc;
++ input;
}
// check if is desired type.
if (! ((type == 1 && isOp(*input) ) ||
(type == 0 && (isDigit(*input) || *input == '+' ||
*input== '-' || *input=='.'))) ) {
err("wrong type of operand/operator", input);
}
Node * n;
if (type == 1) { // operator.
n = new Node(0, *input, type);
n->op_prec = prec(n->op) + prec_base;
++ input;
}
else { // type == 0: operand.
double val;
// sscanf requires no space between sign and value.
sscanf(input, "%lf", &val);
n = new Node(val, 0, type);
if (*input == '+' || *input == '-') ++ input;
if (! (isDigit(*input) || *input == '.')) {
err("incomplete number", input);
}
bool dot_used = false; // allow only one dot.
while ( isDigit(*input) || (*input == '.' && !dot_used)) {
if (*input == '.') dot_used = true;
++ input;
}
while (*input == ')') {
prec_base -= prec_base_inc;
++ input;
}
}
return n;
}
void buildAST(const char * input, Node *& root) {
root = getNextToken(input, 0);
while (1) {
Node * opt = getNextToken(input, 1);
if (! opt) return; // end of input.
Node * opd = getNextToken(input, 0);
if (root->type == 0 || opt->op_prec <= root->op_prec) {
opt->left = root;
opt->right = opd;
root = opt;
} else {
Node * n = root;
while (1) {
if (n->right->type == 0 ||
opt->op_prec <= n->right->op_prec) {
opt->left = n->right;
opt->right = opd;
n->right = opt;
break;
} else {
n = n->right;
}
} // end of while
} // end of if
} // end of while
}
double eval(Node * t) {
if (! t) return 0;
if (t->type == 0) return t->val; // t is operand.
// t is operator.
if (t->op == '+') return eval(t->left) + eval(t->right);
if (t->op == '-') return eval(t->left) - eval(t->right);
if (t->op == '*') return eval(t->left) * eval(t->right);
if (t->op == '/') return eval(t->left) / eval(t->right);
if (t->op == '^') return pow(eval(t->left), eval(t->right));
}
public:
Solution() { prec_base = 0; }
~Solution() { /* destroy AST. */ }
double calc(const char * s) {
p0 = s; // record start pointer position.
Node * p = NULL;
buildAST(s, p);
dump(p); puts("");
return eval(p);
}
};
int main() {
const char * input = "(1 + 2)*((3-1)- 3.5) + 4^2";
Solution s;
cout << "Solution 1: " << s.calc(input) << endl;
return 0;
}
我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
#include
#include
using namespace std;
struct Node {
double val;
char op;
int op_prec; // precedence of operator
int type; // 0 - operand, 1 - operator
Node * left;
Node * right;
Node(double _val, char _op, int _type) : val(_val), op(_op),
type(_type), left(NULL), right(NULL) {}
};
class Solution {
private:
int prec_base;
const char * p0; // record start position of input string.
void err(char * msg, const char * p) {
printf("input error: %s, at input position %d\n", msg, p - p0);
printf("%s\n", p0);
for (int i = 0, len = p - p0; i < len; ++ i) putchar(' ');
printf("^\n");
exit(1);
}
void dump_node(Node * n) {
if (n->type == 0) printf(" %.1lf ", n->val);
else printf(" %c ", n->op);
}
void dump(Node * n) {
if (! n) return;
if (! n->left && ! n->right) {
dump_node(n);
return;
}
printf("(");
dump(n->left);
dump_node(n);
dump(n->right);
printf(")");
}
int prec(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
if (op == '^') return 3;
return 0;
}
int isOp(char c) {
return (c == '+' || c == '-' || c == '*' ||
c == '/' || c == '^');
}
int isDigit(char c) { return c >= '0' && c <= '9'; }
// type - desired type of new token. 0 - operand, 1 - operator.
Node * getNextToken(const char *& input, int type) {
const int prec_base_inc = 4; // 1 + max(op prec)
while (isspace(*input)) ++ input; // skips spaces.
if (! *input) return NULL; // end of input.
while (*input == '(') {
prec_base += prec_base_inc;
++ input;
}
// check if is desired type.
if (! ((type == 1 && isOp(*input) ) ||
(type == 0 && (isDigit(*input) || *input == '+' ||
*input== '-' || *input=='.'))) ) {
err("wrong type of operand/operator", input);
}
Node * n;
if (type == 1) { // operator.
n = new Node(0, *input, type);
n->op_prec = prec(n->op) + prec_base;
++ input;
}
else { // type == 0: operand.
double val;
// sscanf requires no space between sign and value.
sscanf(input, "%lf", &val);
n = new Node(val, 0, type);
if (*input == '+' || *input == '-') ++ input;
if (! (isDigit(*input) || *input == '.')) {
err("incomplete number", input);
}
bool dot_used = false; // allow only one dot.
while ( isDigit(*input) || (*input == '.' && !dot_used)) {
if (*input == '.') dot_used = true;
++ input;
}
while (*input == ')') {
prec_base -= prec_base_inc;
++ input;
}
}
return n;
}
void buildAST(const char * input, Node *& root) {
root = getNextToken(input, 0);
while (1) {
Node * opt = getNextToken(input, 1);
if (! opt) return; // end of input.
Node * opd = getNextToken(input, 0);
if (root->type == 0 || opt->op_prec <= root->op_prec) {
opt->left = root;
opt->right = opd;
root = opt;
} else {
Node * n = root;
while (1) {
if (n->right->type == 0 ||
opt->op_prec <= n->right->op_prec) {
opt->left = n->right;
opt->right = opd;
n->right = opt;
break;
} else {
n = n->right;
}
} // end of while
} // end of if
} // end of while
}
double eval(Node * t) {
if (! t) return 0;
if (t->type == 0) return t->val; // t is operand.
// t is operator.
if (t->op == '+') return eval(t->left) + eval(t->right);
if (t->op == '-') return eval(t->left) - eval(t->right);
if (t->op == '*') return eval(t->left) * eval(t->right);
if (t->op == '/') return eval(t->left) / eval(t->right);
if (t->op == '^') return pow(eval(t->left), eval(t->right));
}
public:
Solution() { prec_base = 0; }
~Solution() { /* destroy AST. */ }
double calc(const char * s) {
p0 = s; // record start pointer position.
Node * p = NULL;
buildAST(s, p);
dump(p); puts("");
return eval(p);
}
};
int main() {
const char * input = "(1 + 2)*((3-1)- 3.5) + 4^2";
Solution s;
cout << "Solution 1: " << s.calc(input) << endl;
return 0;
}
I*s
57 楼
三个主要函数: getNextToken(), buildAST(), eval(). buildAST() 可以是iteration
, eval()是recursion.
, eval()是recursion.
y*x
58 楼
写了个JavaScript的，想法跟二爷一开始的一样，扫两遍，一遍处理+-， 一遍处理*/
function getnum(str){
var n = str.split(/[+\-]+/);
var c = str.split(/[0-9\*\/]+/);
for(var i=0; i
}
for(var j=0; j
}
return n[j];
}
function getmdnum(str){
var n = str.split(/[\*\/]/);
var c = str.split(/[0-9]+/);
if(n.length==1) return n[0]-0;
for(var i=0; i
}
return n[i];
}
function cal(num1, num2, c){
var n1 = num1 -'0';
var n2 = num2 -'0';
switch(c){
case "+":
return n1+n2;
case "-":
return n1-n2;
case "*":
return n1*n2;
case "/":
return n1/n2;
default:
return "Error";
}
}
function getnum(str){
var n = str.split(/[+\-]+/);
var c = str.split(/[0-9\*\/]+/);
for(var i=0; i
}
for(var j=0; j
}
return n[j];
}
function getmdnum(str){
var n = str.split(/[\*\/]/);
var c = str.split(/[0-9]+/);
if(n.length==1) return n[0]-0;
for(var i=0; i
}
return n[i];
}
function cal(num1, num2, c){
var n1 = num1 -'0';
var n2 = num2 -'0';
switch(c){
case "+":
return n1+n2;
case "-":
return n1-n2;
case "*":
return n1*n2;
case "/":
return n1/n2;
default:
return "Error";
}
}
w*p
59 楼
我在隔壁也问了一句这个，被人华丽丽的鄙视了 说是学过compiler课。
低头确实还给老师了。
stack 和cursive 都写了下，还是stack思路清晰简洁。
看看思路，code未必是bug free 的。
http://www.strchr.com/expression_evaluator
http://compsci.ca/v3/viewtopic.php?t=21703
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
低头确实还给老师了。
stack 和cursive 都写了下，还是stack思路清晰简洁。
看看思路，code未必是bug free 的。
http://www.strchr.com/expression_evaluator
http://compsci.ca/v3/viewtopic.php?t=21703
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
f*7
60 楼
题目一出，我就傻眼了，就知道完蛋了。。。
这题目正好是隔壁BB Onsite面经第二题
给一个表达式，计算返回值，不带括号
例子
"7-12/6"
"1000-5*6/3*2+1"
写了半天，问对方，对吗？ 多方说，你说呢。。。
祝大家好运吧，哪个大牛给个链接
这题目正好是隔壁BB Onsite面经第二题
给一个表达式，计算返回值，不带括号
例子
"7-12/6"
"1000-5*6/3*2+1"
写了半天，问对方，对吗？ 多方说，你说呢。。。
祝大家好运吧，哪个大牛给个链接
p*2
61 楼
看了一下。这题你怎么做的？
感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
a*o
62 楼
stack就行了,或者搞个temp variable
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
h*0
63 楼
2爷您的想法和我之前onsite BB的想法一样。。 结果面试官压根不屌我。 必须用
recursive。 我说recursive不好，被华丽丽的鄙视了。。。
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
recursive。 我说recursive不好，被华丽丽的鄙视了。。。
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
p*2
64 楼
stack更简单吗？
【在 a***o 的大作中提到】
: stack就行了,或者搞个temp variable
p*2
65 楼
recursive怎么搞呀？
【在 h*******0 的大作中提到】
: 2爷您的想法和我之前onsite BB的想法一样。。 结果面试官压根不屌我。 必须用
: recursive。 我说recursive不好，被华丽丽的鄙视了。。。
f*7
66 楼
二爷这题我没见过，硬着头皮写recursive，思路都不对，今天就问了这一题。。。
有相关讲解的链接吗？
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
有相关讲解的链接吗？
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
h*0
67 楼
我当时也没想出来。 然后我和他说，我这个方法比recursive好。。 我说recursive可
能会out of memory。 人家根本不同意我的说法。
【在 p*****2 的大作中提到】
:
: recursive怎么搞呀？
能会out of memory。 人家根本不同意我的说法。
【在 p*****2 的大作中提到】
:
: recursive怎么搞呀？
h*0
68 楼
我觉得如果见到没见过的题就要赶紧研究。。 弄不好就是你下一道题。。 这题其实挺
不好写的
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
不好写的
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
p*2
69 楼
我大概的想法
1000-5*6/3*2+1
用个双向链表
1000 - 5 * 6 / 3 * 2 + 1
第一遍算乘除， 比如 看到第一个 ＊ 就把prev * next 然后把5*6拿掉，把结果30放
进去，就成了
1000 - 30 / 3 * 2 + 1
第二遍算加减就从头算到尾就可以了
想想有没有什么更简单的办法。
【在 f*******7 的大作中提到】
: 二爷这题我没见过，硬着头皮写recursive，思路都不对，今天就问了这一题。。。
: 有相关讲解的链接吗？
a*o
70 楼
搞俩variable就行了,一个存之前的数,
一个存当前的数,碰到乘除,更新当前的数,碰到加减更新之前的数
【在 p*****2 的大作中提到】
:
: 我大概的想法
: 1000-5*6/3*2+1
: 用个双向链表
: 1000 - 5 * 6 / 3 * 2 + 1
: 第一遍算乘除， 比如 看到第一个 ＊ 就把prev * next 然后把5*6拿掉，把结果30放
: 进去，就成了
: 1000 - 30 / 3 * 2 + 1
: 第二遍算加减就从头算到尾就可以了
: 想想有没有什么更简单的办法。
一个存当前的数,碰到乘除,更新当前的数,碰到加减更新之前的数
【在 p*****2 的大作中提到】
:
: 我大概的想法
: 1000-5*6/3*2+1
: 用个双向链表
: 1000 - 5 * 6 / 3 * 2 + 1
: 第一遍算乘除， 比如 看到第一个 ＊ 就把prev * next 然后把5*6拿掉，把结果30放
: 进去，就成了
: 1000 - 30 / 3 * 2 + 1
: 第二遍算加减就从头算到尾就可以了
: 想想有没有什么更简单的办法。
p*e
71 楼
搞了个复杂的。。
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from
stdin).
#include
using namespace std;
bool OpHigherOrder(char c1, char c2)
{
if(c1 != '(' && c2 == ')')
return true;
else if(c1 == '(')
return false;
else if((c1 == '*' || c1 == '/'))
return true;
else if((c1 == '+' || c1 == '-') && (c2 == '+' || c2 == '-'))
return true;
else
return false;
}
double CalOp(double e1, char op, double e2)
{
switch(op)
{
case '+':
return e1 + e2;
case '-':
return e1 - e2;
case '*':
return e1 * e2;
case '/':
return e1 / e2;
}
}
double CalExpression(string a)
{
stack num;
stack op;
int numpos = 0;
for(int i = 0; i < a.length(); i++)
{
if(a[i] == ' ')
{
a.erase(i, 1);
i--;
continue;
}
if((a[i]>='0' && a[i]<='9') || a[i] == '.')
{
continue;
}
if(a[i] == '(')
{
op.push('(');
numpos = i + 1;
continue;
}
if(numpos < i)
{
num.push(atof(a.substr(numpos, i - numpos).c_str()));
}
while(op.size() > 0 && num.size()>1)
{
if(OpHigherOrder(op.top(), a[i]))
{
double right = num.top();
num.pop();
double left = num.top();
num.pop();
num.push(CalOp(left, op.top(), right));
op.pop();
}
else
{
break;
}
}
if(a[i] == ')')
{
op.pop();
}
else
op.push(a[i]);
numpos = i + 1;
}
if(numpos < a.length())
num.push(atof(a.substr(numpos).c_str()));
while(op.size() > 0 && num.size()>1)
{
double right = num.top();
num.pop();
double left = num.top();
num.pop();
num.push(CalOp(left, op.top(), right));
op.pop();
}
return num.top();
}
int main() {
// Start typing your code here...
string s("12+5*62/2-3*(5+3*(5+6))");
cout << CalExpression(s) << endl;
return 0;
}
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from
stdin).
#include
using namespace std;
bool OpHigherOrder(char c1, char c2)
{
if(c1 != '(' && c2 == ')')
return true;
else if(c1 == '(')
return false;
else if((c1 == '*' || c1 == '/'))
return true;
else if((c1 == '+' || c1 == '-') && (c2 == '+' || c2 == '-'))
return true;
else
return false;
}
double CalOp(double e1, char op, double e2)
{
switch(op)
{
case '+':
return e1 + e2;
case '-':
return e1 - e2;
case '*':
return e1 * e2;
case '/':
return e1 / e2;
}
}
double CalExpression(string a)
{
stack
stack
int numpos = 0;
for(int i = 0; i < a.length(); i++)
{
if(a[i] == ' ')
{
a.erase(i, 1);
i--;
continue;
}
if((a[i]>='0' && a[i]<='9') || a[i] == '.')
{
continue;
}
if(a[i] == '(')
{
op.push('(');
numpos = i + 1;
continue;
}
if(numpos < i)
{
num.push(atof(a.substr(numpos, i - numpos).c_str()));
}
while(op.size() > 0 && num.size()>1)
{
if(OpHigherOrder(op.top(), a[i]))
{
double right = num.top();
num.pop();
double left = num.top();
num.pop();
num.push(CalOp(left, op.top(), right));
op.pop();
}
else
{
break;
}
}
if(a[i] == ')')
{
op.pop();
}
else
op.push(a[i]);
numpos = i + 1;
}
if(numpos < a.length())
num.push(atof(a.substr(numpos).c_str()));
while(op.size() > 0 && num.size()>1)
{
double right = num.top();
num.pop();
double left = num.top();
num.pop();
num.push(CalOp(left, op.top(), right));
op.pop();
}
return num.top();
}
int main() {
// Start typing your code here...
string s("12+5*62/2-3*(5+3*(5+6))");
cout << CalExpression(s) << endl;
return 0;
}
p*2
72 楼
1000-5*6/3*2+1
recursion的话
1000 － 然后往后找到 ＋， － 或者end
变成
1000- f(5*6/3*2) + 1
主要是纪录＋－的位置。比如上边的例子，4 13
然后分段算 f(0,3) - f(5, 12) + f(14)
recursion的话
1000 － 然后往后找到 ＋， － 或者end
变成
1000- f(5*6/3*2) + 1
主要是纪录＋－的位置。比如上边的例子，4 13
然后分段算 f(0,3) - f(5, 12) + f(14)
h*8
73 楼
尝试构造一个对应的AST？不知道可不可以
p*2
74 楼
应该可以。就是写起来不知道是不是容易bug free。你可以写写看看。
【在 a***o 的大作中提到】
: 搞俩variable就行了,一个存之前的数,
: 一个存当前的数,碰到乘除,更新当前的数,碰到加减更新之前的数
o*d
75 楼
我记得这个是我在国内尚数据结构时stack的李子(当然可能各个学校不一样),参考严蔚
敏的书
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
敏的书
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
o*d
76 楼
另外,这个我在careercup上见过google也考过似乎
【在 o***d 的大作中提到】
: 我记得这个是我在国内尚数据结构时stack的李子(当然可能各个学校不一样),参考严蔚
: 敏的书
【在 o***d 的大作中提到】
: 我记得这个是我在国内尚数据结构时stack的李子(当然可能各个学校不一样),参考严蔚
: 敏的书
b*u
77 楼
试着写了一个递归的
思路： 每个recursion的开始有一个factor，一个当前operand和一个之前乘/除号
首先把operand = operand 乘除 factor
然后，如果下一符号是加减，则返回 operand 加减下一recursion（factor=1， 乘）
如果下一符号是乘除，则返回下一recursion (factor=当前operand, 下一符号）
(on a second thought, 这个其实也就是实现了一个stack的功能，递归即stack)
#include "stdafx.h"
#include
#include
#include
using namespace std;
int stringCalculator(string input, int factor, char sign)
{
int len = input.length();
if (len == 0) return 0;
int i = 0;
while (i< len && input[i]>='0' && input[i]<='9')
{
++i;
}
int rightEnd = min (len, i);
int operand = atoi(input.substr(0,rightEnd).c_str());
if (sign == '*')
operand *= factor;
else
operand /= factor;
if (i == len)
return operand;
else
{
switch (input[i])
{
case '+':
return operand+stringCalculator(input.substr(i+1), 1, '*');
case '-':
return operand-stringCalculator(input.substr(i+1), 1, '*');
default:
return stringCalculator(input.substr(i+1), operand, input[i]);
break;
}
}
}
int calculator (string input)
{
return stringCalculator(input,1,'*');
}
int _tmain(int argc, _TCHAR* argv[])
{
string test = "1+2*3";
cout << calculator (test);
cin.get();
return 0;
}
思路： 每个recursion的开始有一个factor，一个当前operand和一个之前乘/除号
首先把operand = operand 乘除 factor
然后，如果下一符号是加减，则返回 operand 加减下一recursion（factor=1， 乘）
如果下一符号是乘除，则返回下一recursion (factor=当前operand, 下一符号）
(on a second thought, 这个其实也就是实现了一个stack的功能，递归即stack)
#include "stdafx.h"
#include
#include
#include
using namespace std;
int stringCalculator(string input, int factor, char sign)
{
int len = input.length();
if (len == 0) return 0;
int i = 0;
while (i< len && input[i]>='0' && input[i]<='9')
{
++i;
}
int rightEnd = min (len, i);
int operand = atoi(input.substr(0,rightEnd).c_str());
if (sign == '*')
operand *= factor;
else
operand /= factor;
if (i == len)
return operand;
else
{
switch (input[i])
{
case '+':
return operand+stringCalculator(input.substr(i+1), 1, '*');
case '-':
return operand-stringCalculator(input.substr(i+1), 1, '*');
default:
return stringCalculator(input.substr(i+1), operand, input[i]);
break;
}
}
}
int calculator (string input)
{
return stringCalculator(input,1,'*');
}
int _tmain(int argc, _TCHAR* argv[])
{
string test = "1+2*3";
cout << calculator (test);
cin.get();
return 0;
}
m*1
78 楼
电面考这个，要求有点高啊，写计算器是以前学做编译原理搞语法和词法分析的小
project哎
project哎
w*x
79 楼
int mul(const char*& p);
int num(const char*& p);
int Add(const char*& p)
{
int res = mul(p);
while (*p == '+' || *p == '-')
{
if (*p == '+')
res += mul(++p);
else
res -= mul(++p);
}
return res;
}
int mul(const char*& p)
{
int res = num(p);
while (*p == '*' || *p == '/')
{
if (*p == '*')
res *= num(++p);
else
res /= num(++p);
}
return res;
}
int num(const char*& p)
{
bool bNeg = false;
if (*p == '-')
{
bNeg = true;
p++;
}
int res = 0;
while (*p >= '0' && *p <= '9')
res = res*10 + *p++ - '0';
return bNeg ? -res : res;
}
递归下降
Add = mul | (+- mul)*
mul = num | (+- num)*
num = (+-)[0-9]*
int num(const char*& p);
int Add(const char*& p)
{
int res = mul(p);
while (*p == '+' || *p == '-')
{
if (*p == '+')
res += mul(++p);
else
res -= mul(++p);
}
return res;
}
int mul(const char*& p)
{
int res = num(p);
while (*p == '*' || *p == '/')
{
if (*p == '*')
res *= num(++p);
else
res /= num(++p);
}
return res;
}
int num(const char*& p)
{
bool bNeg = false;
if (*p == '-')
{
bNeg = true;
p++;
}
int res = 0;
while (*p >= '0' && *p <= '9')
res = res*10 + *p++ - '0';
return bNeg ? -res : res;
}
递归下降
Add = mul | (+- mul)*
mul = num | (+- num)*
num = (+-)[0-9]*
j*y
80 楼
int value(int a, int b, char c)
{
if(c == '+') return a + b;
if(c == '-') return a - b;
if(c == '*') return a * b;
if(c == '/') return a / b;
}
int expression(vector s)
{
if(s.size() == 0)
{
return 0;
}
stack operand;
stack operators;
operand.push(atoi(s[0].c_str()));
for(int i = 1; i < s.size(); ++i)
{
if(isdigit(s[i][0]))
{
operand.push(atoi(s[i].c_str()));
}
else
{ char c = s[i][0];
if(c == '*' || c == '/')
{
int a = atoi(s[++i].c_str());
a = value(operand.top(), a, c);
operand.pop();
operand.push(a);
}
else
{
if(operand.size() == 2)
{
int b = operand.top();
operand.pop();
int a = operand.top();
operand.pop();
operand.push(value(a, b, operators.top()));
operators.pop();
operators.push(c);
}
else
{
operators.push(c);
}
}
}
}
if(operand.size() == 2)
{
int b = operand.top();
operand.pop();
int a = operand.top();
return value(a, b, operators.top());
}
else
{
return operand.top();
}
}
感觉不用 stack也可以， 因为 stack里面只有一个或者两个 item
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
{
if(c == '+') return a + b;
if(c == '-') return a - b;
if(c == '*') return a * b;
if(c == '/') return a / b;
}
int expression(vector
{
if(s.size() == 0)
{
return 0;
}
stack
stack
operand.push(atoi(s[0].c_str()));
for(int i = 1; i < s.size(); ++i)
{
if(isdigit(s[i][0]))
{
operand.push(atoi(s[i].c_str()));
}
else
{ char c = s[i][0];
if(c == '*' || c == '/')
{
int a = atoi(s[++i].c_str());
a = value(operand.top(), a, c);
operand.pop();
operand.push(a);
}
else
{
if(operand.size() == 2)
{
int b = operand.top();
operand.pop();
int a = operand.top();
operand.pop();
operand.push(value(a, b, operators.top()));
operators.pop();
operators.push(c);
}
else
{
operators.push(c);
}
}
}
}
if(operand.size() == 2)
{
int b = operand.top();
operand.pop();
int a = operand.top();
return value(a, b, operators.top());
}
else
{
return operand.top();
}
}
感觉不用 stack也可以， 因为 stack里面只有一个或者两个 item
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
p*2
81 楼
def cal(str:String):Int={
val numbers=str.split("[+-/*]").map(_.toInt)
val operators=str.filterNot(_.isDigit)
var result=numbers(0)
for(icase '+' => result+=numbers(i+1)
case '-' => result-=numbers(i+1)
case '*' => result*=numbers(i+1)
case '/' => result/=numbers(i+1)
}
result
}
def solve(str:String):Int={
val plusminus= -1 +: (for(istr(i)=='-') yield i)
var sb=new StringBuilder()
for(isb.append(cal(str.slice(plusminus(i-1)+1,plusminus(i))))
sb.append(str(plusminus(i)))
}
sb.append(cal(str.slice(plusminus.last+1, str.length)))
cal(sb.toString)
}
val numbers=str.split("[+-/*]").map(_.toInt)
val operators=str.filterNot(_.isDigit)
var result=numbers(0)
for(icase '+' => result+=numbers(i+1)
case '-' => result-=numbers(i+1)
case '*' => result*=numbers(i+1)
case '/' => result/=numbers(i+1)
}
result
}
def solve(str:String):Int={
val plusminus= -1 +: (for(istr(i)=='-') yield i)
var sb=new StringBuilder()
for(isb.append(cal(str.slice(plusminus(i-1)+1,plusminus(i))))
sb.append(str(plusminus(i)))
}
sb.append(cal(str.slice(plusminus.last+1, str.length)))
cal(sb.toString)
}
h*0
82 楼
为啥感觉你代码写的这么优美呢？ 难道是排版排的好？ ：）
【在 w****x 的大作中提到】
: int mul(const char*& p);
: int num(const char*& p);
: int Add(const char*& p)
: {
: int res = mul(p);
: while (*p == '+' || *p == '-')
: {
: if (*p == '+')
: res += mul(++p);
: else
【在 w****x 的大作中提到】
: int mul(const char*& p);
: int num(const char*& p);
: int Add(const char*& p)
: {
: int res = mul(p);
: while (*p == '+' || *p == '-')
: {
: if (*p == '+')
: res += mul(++p);
: else
q*s
83 楼
这个不是逆波兰吗？
★ 发自iPhone App: ChineseWeb 7.8
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
★ 发自iPhone App: ChineseWeb 7.8
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
a*o
84 楼
写的漂亮,可能C比较简洁
【在 h*******0 的大作中提到】
: 为啥感觉你代码写的这么优美呢？ 难道是排版排的好？ ：）
【在 h*******0 的大作中提到】
: 为啥感觉你代码写的这么优美呢？ 难道是排版排的好？ ：）
e*e
85 楼
凑个热闹!
public int calculate( String[] in, int sIdx ) {
if ( sIdx == in.length - 1)
return toInt( in[sIdx] );
int addOrMinus = getAddOrMinusSign( in[sIdx + 1] );
if ( addOrMinus != 0 ) {
if ( sIdx + 2 == in.length - 1 || getAddOrMinusSign( in[sIdx + 3] ) !=
0 ) {
in[sIdx+2] = toStr( toInt( in[sIdx] ) + addOrMinus*toInt( in[sIdx+
2] ) );
return calculate( in, sIdx + 2 );
} else {
calMulOrDivAndSetBack( in, sIdx+2 );
in[sIdx+3] = in[sIdx+1];
in[sIdx+2] = in[sIdx];
return calculate( in, sIdx + 2 );
}
}
calMulOrDivAndSetBack( in, sIdx );
return calculate( in, sIdx + 2 );
}
private int getAddOrMinusSign( String s ){
if ( "+".equals( s ) )
return 1;
else if ( "-".equals( s ) )
return -1;
return 0;
}
private void calMulOrDivAndSetBack( String[] in, int idx ) {
if ( "*".equals( in[idx + 1] ) )
in[idx+2] = toStr( toInt( in[idx] ) * toInt( in[idx+2] ) );
else
in[idx+2] = toStr( toInt( in[idx] ) / toInt( in[idx+2] ) );
}
private int toInt( String s ){
return Integer.parseInt( s );
}
private String toStr( Integer i ) {
return Integer.toString( i );
}
public int calculate( String[] in, int sIdx ) {
if ( sIdx == in.length - 1)
return toInt( in[sIdx] );
int addOrMinus = getAddOrMinusSign( in[sIdx + 1] );
if ( addOrMinus != 0 ) {
if ( sIdx + 2 == in.length - 1 || getAddOrMinusSign( in[sIdx + 3] ) !=
0 ) {
in[sIdx+2] = toStr( toInt( in[sIdx] ) + addOrMinus*toInt( in[sIdx+
2] ) );
return calculate( in, sIdx + 2 );
} else {
calMulOrDivAndSetBack( in, sIdx+2 );
in[sIdx+3] = in[sIdx+1];
in[sIdx+2] = in[sIdx];
return calculate( in, sIdx + 2 );
}
}
calMulOrDivAndSetBack( in, sIdx );
return calculate( in, sIdx + 2 );
}
private int getAddOrMinusSign( String s ){
if ( "+".equals( s ) )
return 1;
else if ( "-".equals( s ) )
return -1;
return 0;
}
private void calMulOrDivAndSetBack( String[] in, int idx ) {
if ( "*".equals( in[idx + 1] ) )
in[idx+2] = toStr( toInt( in[idx] ) * toInt( in[idx+2] ) );
else
in[idx+2] = toStr( toInt( in[idx] ) / toInt( in[idx+2] ) );
}
private int toInt( String s ){
return Integer.parseInt( s );
}
private String toStr( Integer i ) {
return Integer.toString( i );
}
w*x
86 楼
可能因为我比较帅吧
【在 h*******0 的大作中提到】
: 为啥感觉你代码写的这么优美呢？ 难道是排版排的好？ ：）
l*a
87 楼
看linkedin不像啊
【在 w****x 的大作中提到】
:
: 可能因为我比较帅吧
【在 w****x 的大作中提到】
:
: 可能因为我比较帅吧
w*x
88 楼
等等，我马上换成刘德华的
【在 l*****a 的大作中提到】
: 看linkedin不像啊
s*s
89 楼
贴个java recursive的吧。
float compute(String exp) {
if(exp == null || exp.length() == 0) return 0;
int plusPos = exp.indexOf('+');
int minusPos = exp.indexOf('-');
if(plusPos < 0 && minusPos < 0) return convert(exp);
if(plusPos < 0 || (minusPos > 0 && minusPos < plusPos))
return convert(exp.substring(0, minusPos)) - compute(exp.
substring(minusPos+1));
if(minusPos < 0 || (plusPos > 0 && plusPos < minusPos))
return convert(exp.substring(0, plusPos)) + compute(exp.
substring(plusPos+1));
return 0;
}
float convert(String exp){
float res = 1;
float curr = 0;
boolean isProduct = true;
for(int i = 0; i < exp.length(); i++){
if(exp.charAt(i) == '*' || exp.charAt(i) == '/'){
if(isProduct)
res = res * curr;
else {
if(curr == 0)
throw new IllegalArgumentException("Denominator is
0");
else res = res/curr;
}
curr = 0;
isProduct = (exp.charAt(i) == '*');
} else {
curr = curr * 10 + (float)(exp.charAt(i) - '0');
}
}
if(isProduct)
res = res * curr;
else {
if(curr == 0)
throw new IllegalArgumentException("Denominator is 0");
else res = res/curr;
}
return res;
}
float compute(String exp) {
if(exp == null || exp.length() == 0) return 0;
int plusPos = exp.indexOf('+');
int minusPos = exp.indexOf('-');
if(plusPos < 0 && minusPos < 0) return convert(exp);
if(plusPos < 0 || (minusPos > 0 && minusPos < plusPos))
return convert(exp.substring(0, minusPos)) - compute(exp.
substring(minusPos+1));
if(minusPos < 0 || (plusPos > 0 && plusPos < minusPos))
return convert(exp.substring(0, plusPos)) + compute(exp.
substring(plusPos+1));
return 0;
}
float convert(String exp){
float res = 1;
float curr = 0;
boolean isProduct = true;
for(int i = 0; i < exp.length(); i++){
if(exp.charAt(i) == '*' || exp.charAt(i) == '/'){
if(isProduct)
res = res * curr;
else {
if(curr == 0)
throw new IllegalArgumentException("Denominator is
0");
else res = res/curr;
}
curr = 0;
isProduct = (exp.charAt(i) == '*');
} else {
curr = curr * 10 + (float)(exp.charAt(i) - '0');
}
}
if(isProduct)
res = res * curr;
else {
if(curr == 0)
throw new IllegalArgumentException("Denominator is 0");
else res = res/curr;
}
return res;
}
x*6
90 楼
先把表达式转换成operand和operator的string[],再转换成postfix notation，最后用
一个stack来帮助计算
一个stack来帮助计算
p*2
91 楼
这个看起来不错。
【在 w****x 的大作中提到】
: int mul(const char*& p);
: int num(const char*& p);
: int Add(const char*& p)
: {
: int res = mul(p);
: while (*p == '+' || *p == '-')
: {
: if (*p == '+')
: res += mul(++p);
: else
s*0
92 楼
向 Edsger Dijkstra 先生致敬：
http://en.wikipedia.org/wiki/Shunting-yard_algorithm
http://en.wikipedia.org/wiki/Shunting-yard_algorithm
l*8
93 楼
double readNumber(const char * &str) {
double num;
sscanf(str, "%lf", &num);
for (++str; isdigit(*str) || *str == '.'; ++str)
;
return num;
}
double calculate(const char * str) {
if (*str == '\0') return 0.0;
double result = 1.0;
char op = '*';
while (op == '*' || op == '/') {
if (op == '*')
result *= readNumber(str);
else
result /= readNumber(str);
op = *str++;
}
return result + calculate(--str);
}
double num;
sscanf(str, "%lf", &num);
for (++str; isdigit(*str) || *str == '.'; ++str)
;
return num;
}
double calculate(const char * str) {
if (*str == '\0') return 0.0;
double result = 1.0;
char op = '*';
while (op == '*' || op == '/') {
if (op == '*')
result *= readNumber(str);
else
result /= readNumber(str);
op = *str++;
}
return result + calculate(--str);
}
l*8
94 楼
测试案例：
-3-4.3+5.05*2/4-4.10/5+3 = -2.595
【在 l*********8 的大作中提到】
: double readNumber(const char * &str) {
: double num;
: sscanf(str, "%lf", &num);
: for (++str; isdigit(*str) || *str == '.'; ++str)
: ;
: return num;
: }
: double calculate(const char * str) {
: if (*str == '\0') return 0.0;
: double result = 1.0;
-3-4.3+5.05*2/4-4.10/5+3 = -2.595
【在 l*********8 的大作中提到】
: double readNumber(const char * &str) {
: double num;
: sscanf(str, "%lf", &num);
: for (++str; isdigit(*str) || *str == '.'; ++str)
: ;
: return num;
: }
: double calculate(const char * str) {
: if (*str == '\0') return 0.0;
: double result = 1.0;
l*b
95 楼
学习了...发愁那个减号怎么处理呢...原来是sscanf...哈哈
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
s*0
96 楼
package myutil;
import java.util.Scanner;
import java.util.Stack;
public class ParseExp {
Stack oprand = new Stack();
Stack oprator = new Stack();
static int[] code = new int[256];
static {
code['+'] = 10;
code['-'] = 11;
code['*'] = 20;
code['/'] = 21;
code['^'] = 30;
code['$'] = 0;
code['('] = 100;
code[')'] = 1;
}
public ParseExp() {
}
public Integer parse(String e) {
Scanner s = new Scanner(e + " $");
oprator.push(-1);
while (true) {
if (s.hasNextInt()) {
oprand.push(s.nextInt());
} else if (s.hasNext("[-$+*/^()]")) {
int optr = code[s.next(".").charAt(0)];
while (!oprator.isEmpty() && oprator.peek() > optr) {
int y = oprand.pop();
int x = oprand.pop();
switch (oprator.pop()) {
case 10:
oprand.push(x + y);
break;
case 11:
oprand.push(x - y);
break;
case 20:
oprand.push(x * y);
break;
case 21:
oprand.push(x * y);
break;
case 30:
oprand.push((int) Math.pow(x, y));
break;
}
}
if (optr == 0)
break;
if (optr == 100) {
oprator.push(1);
continue;
} else if (optr == 1) {
oprator.pop();
continue;
} else
oprator.push(optr);
} else {
System.out.println(s.next());
}
}
return oprand.peek();
}
public static void main(String[] args) {
ParseExp p = new ParseExp();
for (String e : new String[] { "1 + 1", "1 + 2 * 3", "1 * 2 + 3",
"1 + 2 * 3 + 4", "2 ^ 8 + 1 * 4", "1 * 4 + 2 ^ 8 - 4",
"( 2 + 3 ) * ( 4 + 6 ) ^ 2" }) {
System.out.println(e + " = " + p.parse(e));
}
}
}
import java.util.Scanner;
import java.util.Stack;
public class ParseExp {
Stack
Stack
static int[] code = new int[256];
static {
code['+'] = 10;
code['-'] = 11;
code['*'] = 20;
code['/'] = 21;
code['^'] = 30;
code['$'] = 0;
code['('] = 100;
code[')'] = 1;
}
public ParseExp() {
}
public Integer parse(String e) {
Scanner s = new Scanner(e + " $");
oprator.push(-1);
while (true) {
if (s.hasNextInt()) {
oprand.push(s.nextInt());
} else if (s.hasNext("[-$+*/^()]")) {
int optr = code[s.next(".").charAt(0)];
while (!oprator.isEmpty() && oprator.peek() > optr) {
int y = oprand.pop();
int x = oprand.pop();
switch (oprator.pop()) {
case 10:
oprand.push(x + y);
break;
case 11:
oprand.push(x - y);
break;
case 20:
oprand.push(x * y);
break;
case 21:
oprand.push(x * y);
break;
case 30:
oprand.push((int) Math.pow(x, y));
break;
}
}
if (optr == 0)
break;
if (optr == 100) {
oprator.push(1);
continue;
} else if (optr == 1) {
oprator.pop();
continue;
} else
oprator.push(optr);
} else {
System.out.println(s.next());
}
}
return oprand.peek();
}
public static void main(String[] args) {
ParseExp p = new ParseExp();
for (String e : new String[] { "1 + 1", "1 + 2 * 3", "1 * 2 + 3",
"1 + 2 * 3 + 4", "2 ^ 8 + 1 * 4", "1 * 4 + 2 ^ 8 - 4",
"( 2 + 3 ) * ( 4 + 6 ) ^ 2" }) {
System.out.println(e + " = " + p.parse(e));
}
}
}
M*l
97 楼
逆波兰表达式吧？用个stack就行了，两年前面试被问过，当时居然正好复习到了～～
http://baike.baidu.com/view/552648.htm
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
http://baike.baidu.com/view/552648.htm
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
p*2
99 楼
longway又出手了。
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
H*s
100 楼
还是这个牛啊！
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
p*2
101 楼
longway的代码向来都是最简洁的。
【在 H****s 的大作中提到】
: 还是这个牛啊！
e*e
102 楼
写了一个infix to postfix，实现起来简单, 不知道思路还真不好想，面试的时候我肯
定想不出来。逆波兰表达式(postfix)evaluation是常见题，我就不贴了.
public List toPostfix(String[] in) {
List pf = new ArrayList();
Stack stack = new Stack();
for ( String s : in ) {
int p = getPrecedence( s );
if ( p == 0 )
pf.add( s );
else if ( stack.empty() )
stack.push( s );
else {
while( !stack.isEmpty() && getPrecedence( stack.peek() ) >= p )
pf.add( stack.pop() );
stack.push( s );
}
}
while( !stack.isEmpty() )
pf.add( stack.pop() );
return pf;
}
private int getPrecedence(String s) {
switch( s ) {
case "*": return 2;
case "/": return 2;
case "+": return 1;
case "-": return 1;
default : return 0;
}
}
【在 M******l 的大作中提到】
: 逆波兰表达式吧？用个stack就行了，两年前面试被问过，当时居然正好复习到了～～
: http://baike.baidu.com/view/552648.htm
定想不出来。逆波兰表达式(postfix)evaluation是常见题，我就不贴了.
public List
List
Stack
for ( String s : in ) {
int p = getPrecedence( s );
if ( p == 0 )
pf.add( s );
else if ( stack.empty() )
stack.push( s );
else {
while( !stack.isEmpty() && getPrecedence( stack.peek() ) >= p )
pf.add( stack.pop() );
stack.push( s );
}
}
while( !stack.isEmpty() )
pf.add( stack.pop() );
return pf;
}
private int getPrecedence(String s) {
switch( s ) {
case "*": return 2;
case "/": return 2;
case "+": return 1;
case "-": return 1;
default : return 0;
}
}
【在 M******l 的大作中提到】
: 逆波兰表达式吧？用个stack就行了，两年前面试被问过，当时居然正好复习到了～～
: http://baike.baidu.com/view/552648.htm
p*2
103 楼
这东西没搞过。回头看看。
【在 e****e 的大作中提到】
: 写了一个infix to postfix，实现起来简单, 不知道思路还真不好想，面试的时候我肯
: 定想不出来。逆波兰表达式(postfix)evaluation是常见题，我就不贴了.
: public List
: List
: Stack
: for ( String s : in ) {
: int p = getPrecedence( s );
: if ( p == 0 )
: pf.add( s );
: else if ( stack.empty() )
l*8
104 楼
谢谢！ 这道题目， 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
d*f
105 楼
20年前你这么回答可能还行
【在 h*******0 的大作中提到】
: 我当时也没想出来。 然后我和他说，我这个方法比recursive好。。 我说recursive可
: 能会out of memory。 人家根本不同意我的说法。
【在 h*******0 的大作中提到】
: 我当时也没想出来。 然后我和他说，我这个方法比recursive好。。 我说recursive可
: 能会out of memory。 人家根本不同意我的说法。
n*e
106 楼
哈哈，这个牛！居然能这么处理。
【在 l*********8 的大作中提到】
: 谢谢！ 这道题目， 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
: 面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
【在 l*********8 的大作中提到】
: 谢谢！ 这道题目， 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
: 面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
I*s
107 楼
最喜欢 wwwyhx的解法: recursive descent.
我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
#include
#include // for pow()
using namespace std;
struct Node {
double val;
char op;
int op_prec; // precedence of operator
int type; // 0 - operand, 1 - operator
Node * left;
Node * right;
Node(double _val, char _op, int _type) : val(_val), op(_op),
type(_type), left(NULL), right(NULL) {}
};
class Solution {
private:
int prec_base;
const char * p0; // record start position of input string.
void err(char * msg, const char * p) {
printf("input error: %s, at input position %d\n", msg, p - p0);
printf("%s\n", p0);
for (int i = 0, len = p - p0; i < len; ++ i) putchar(' ');
printf("^\n");
exit(1);
}
void dump_node(Node * n) {
if (n->type == 0) printf(" %.1lf ", n->val);
else printf(" %c ", n->op);
}
void dump(Node * n) {
if (! n) return;
if (! n->left && ! n->right) {
dump_node(n);
return;
}
printf("(");
dump(n->left);
dump_node(n);
dump(n->right);
printf(")");
}
int prec(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
if (op == '^') return 3;
return 0;
}
int isOp(char c) {
return (c == '+' || c == '-' || c == '*' ||
c == '/' || c == '^');
}
int isDigit(char c) { return c >= '0' && c <= '9'; }
// type - desired type of new token. 0 - operand, 1 - operator.
Node * getNextToken(const char *& input, int type) {
const int prec_base_inc = 4; // 1 + max(op prec)
while (isspace(*input)) ++ input; // skips spaces.
if (! *input) return NULL; // end of input.
while (*input == '(') {
prec_base += prec_base_inc;
++ input;
}
// check if is desired type.
if (! ((type == 1 && isOp(*input) ) ||
(type == 0 && (isDigit(*input) || *input == '+' ||
*input== '-' || *input=='.'))) ) {
err("wrong type of operand/operator", input);
}
Node * n;
if (type == 1) { // operator.
n = new Node(0, *input, type);
n->op_prec = prec(n->op) + prec_base;
++ input;
}
else { // type == 0: operand.
double val;
// sscanf requires no space between sign and value.
sscanf(input, "%lf", &val);
n = new Node(val, 0, type);
if (*input == '+' || *input == '-') ++ input;
if (! (isDigit(*input) || *input == '.')) {
err("incomplete number", input);
}
bool dot_used = false; // allow only one dot.
while ( isDigit(*input) || (*input == '.' && !dot_used)) {
if (*input == '.') dot_used = true;
++ input;
}
while (*input == ')') {
prec_base -= prec_base_inc;
++ input;
}
}
return n;
}
void buildAST(const char * input, Node *& root) {
root = getNextToken(input, 0);
while (1) {
Node * opt = getNextToken(input, 1);
if (! opt) return; // end of input.
Node * opd = getNextToken(input, 0);
if (root->type == 0 || opt->op_prec <= root->op_prec) {
opt->left = root;
opt->right = opd;
root = opt;
} else {
Node * n = root;
while (1) {
if (n->right->type == 0 ||
opt->op_prec <= n->right->op_prec) {
opt->left = n->right;
opt->right = opd;
n->right = opt;
break;
} else {
n = n->right;
}
} // end of while
} // end of if
} // end of while
}
double eval(Node * t) {
if (! t) return 0;
if (t->type == 0) return t->val; // t is operand.
// t is operator.
if (t->op == '+') return eval(t->left) + eval(t->right);
if (t->op == '-') return eval(t->left) - eval(t->right);
if (t->op == '*') return eval(t->left) * eval(t->right);
if (t->op == '/') return eval(t->left) / eval(t->right);
if (t->op == '^') return pow(eval(t->left), eval(t->right));
}
public:
Solution() { prec_base = 0; }
~Solution() { /* destroy AST. */ }
double calc(const char * s) {
p0 = s; // record start pointer position.
Node * p = NULL;
buildAST(s, p);
dump(p); puts("");
return eval(p);
}
};
int main() {
const char * input = "(1 + 2)*((3-1)- 3.5) + 4^2";
Solution s;
cout << "Solution 1: " << s.calc(input) << endl;
return 0;
}
我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
#include
#include
using namespace std;
struct Node {
double val;
char op;
int op_prec; // precedence of operator
int type; // 0 - operand, 1 - operator
Node * left;
Node * right;
Node(double _val, char _op, int _type) : val(_val), op(_op),
type(_type), left(NULL), right(NULL) {}
};
class Solution {
private:
int prec_base;
const char * p0; // record start position of input string.
void err(char * msg, const char * p) {
printf("input error: %s, at input position %d\n", msg, p - p0);
printf("%s\n", p0);
for (int i = 0, len = p - p0; i < len; ++ i) putchar(' ');
printf("^\n");
exit(1);
}
void dump_node(Node * n) {
if (n->type == 0) printf(" %.1lf ", n->val);
else printf(" %c ", n->op);
}
void dump(Node * n) {
if (! n) return;
if (! n->left && ! n->right) {
dump_node(n);
return;
}
printf("(");
dump(n->left);
dump_node(n);
dump(n->right);
printf(")");
}
int prec(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
if (op == '^') return 3;
return 0;
}
int isOp(char c) {
return (c == '+' || c == '-' || c == '*' ||
c == '/' || c == '^');
}
int isDigit(char c) { return c >= '0' && c <= '9'; }
// type - desired type of new token. 0 - operand, 1 - operator.
Node * getNextToken(const char *& input, int type) {
const int prec_base_inc = 4; // 1 + max(op prec)
while (isspace(*input)) ++ input; // skips spaces.
if (! *input) return NULL; // end of input.
while (*input == '(') {
prec_base += prec_base_inc;
++ input;
}
// check if is desired type.
if (! ((type == 1 && isOp(*input) ) ||
(type == 0 && (isDigit(*input) || *input == '+' ||
*input== '-' || *input=='.'))) ) {
err("wrong type of operand/operator", input);
}
Node * n;
if (type == 1) { // operator.
n = new Node(0, *input, type);
n->op_prec = prec(n->op) + prec_base;
++ input;
}
else { // type == 0: operand.
double val;
// sscanf requires no space between sign and value.
sscanf(input, "%lf", &val);
n = new Node(val, 0, type);
if (*input == '+' || *input == '-') ++ input;
if (! (isDigit(*input) || *input == '.')) {
err("incomplete number", input);
}
bool dot_used = false; // allow only one dot.
while ( isDigit(*input) || (*input == '.' && !dot_used)) {
if (*input == '.') dot_used = true;
++ input;
}
while (*input == ')') {
prec_base -= prec_base_inc;
++ input;
}
}
return n;
}
void buildAST(const char * input, Node *& root) {
root = getNextToken(input, 0);
while (1) {
Node * opt = getNextToken(input, 1);
if (! opt) return; // end of input.
Node * opd = getNextToken(input, 0);
if (root->type == 0 || opt->op_prec <= root->op_prec) {
opt->left = root;
opt->right = opd;
root = opt;
} else {
Node * n = root;
while (1) {
if (n->right->type == 0 ||
opt->op_prec <= n->right->op_prec) {
opt->left = n->right;
opt->right = opd;
n->right = opt;
break;
} else {
n = n->right;
}
} // end of while
} // end of if
} // end of while
}
double eval(Node * t) {
if (! t) return 0;
if (t->type == 0) return t->val; // t is operand.
// t is operator.
if (t->op == '+') return eval(t->left) + eval(t->right);
if (t->op == '-') return eval(t->left) - eval(t->right);
if (t->op == '*') return eval(t->left) * eval(t->right);
if (t->op == '/') return eval(t->left) / eval(t->right);
if (t->op == '^') return pow(eval(t->left), eval(t->right));
}
public:
Solution() { prec_base = 0; }
~Solution() { /* destroy AST. */ }
double calc(const char * s) {
p0 = s; // record start pointer position.
Node * p = NULL;
buildAST(s, p);
dump(p); puts("");
return eval(p);
}
};
int main() {
const char * input = "(1 + 2)*((3-1)- 3.5) + 4^2";
Solution s;
cout << "Solution 1: " << s.calc(input) << endl;
return 0;
}
I*s
108 楼
三个主要函数: getNextToken(), buildAST(), eval(). buildAST() 可以是iteration
, eval()是recursion.
, eval()是recursion.
y*x
109 楼
写了个JavaScript的，想法跟二爷一开始的一样，扫两遍，一遍处理+-， 一遍处理*/
function getnum(str){
var n = str.split(/[+\-]+/);
var c = str.split(/[0-9\*\/]+/);
for(var i=0; i
}
for(var j=0; j
}
return n[j];
}
function getmdnum(str){
var n = str.split(/[\*\/]/);
var c = str.split(/[0-9]+/);
if(n.length==1) return n[0]-0;
for(var i=0; i
}
return n[i];
}
function cal(num1, num2, c){
var n1 = num1 -'0';
var n2 = num2 -'0';
switch(c){
case "+":
return n1+n2;
case "-":
return n1-n2;
case "*":
return n1*n2;
case "/":
return n1/n2;
default:
return "Error";
}
}
function getnum(str){
var n = str.split(/[+\-]+/);
var c = str.split(/[0-9\*\/]+/);
for(var i=0; i
}
for(var j=0; j
}
return n[j];
}
function getmdnum(str){
var n = str.split(/[\*\/]/);
var c = str.split(/[0-9]+/);
if(n.length==1) return n[0]-0;
for(var i=0; i
}
return n[i];
}
function cal(num1, num2, c){
var n1 = num1 -'0';
var n2 = num2 -'0';
switch(c){
case "+":
return n1+n2;
case "-":
return n1-n2;
case "*":
return n1*n2;
case "/":
return n1/n2;
default:
return "Error";
}
}
w*p
110 楼
我在隔壁也问了一句这个，被人华丽丽的鄙视了 说是学过compiler课。
低头确实还给老师了。
stack 和cursive 都写了下，还是stack思路清晰简洁。
看看思路，code未必是bug free 的。
http://www.strchr.com/expression_evaluator
http://compsci.ca/v3/viewtopic.php?t=21703
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
低头确实还给老师了。
stack 和cursive 都写了下，还是stack思路清晰简洁。
看看思路，code未必是bug free 的。
http://www.strchr.com/expression_evaluator
http://compsci.ca/v3/viewtopic.php?t=21703
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
d*r
111 楼
先转换成postfix再用stack来实现就容易很多吧。
u*o
112 楼
mark一下，赶脚这楼里出手的大牛们很多呀
n*e
113 楼
这code，店面写出来不太现实吧。。。
考.
【在 I**********s 的大作中提到】
: 最喜欢 wwwyhx的解法: recursive descent.
: 我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
: 号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
: 及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
: #include
: #include // for pow()
: using namespace std;
: struct Node {
: double val;
: char op;
考.
【在 I**********s 的大作中提到】
: 最喜欢 wwwyhx的解法: recursive descent.
: 我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
: 号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
: 及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
: #include
: #include
: using namespace std;
: struct Node {
: double val;
: char op;
z*8
114 楼
我觉得是啊， coding很简单
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
V*r
115 楼
>>> s = "1000-5*6/3*2+1"
>>> eval(s)
981
>>> eval(s)
981
s*u
116 楼
stack 用来做postfix简单，prefix要用两个或者倒序遍历字符串。没看出写中缀用
stack很简单
【在 z*********8 的大作中提到】
: 我觉得是啊， coding很简单
stack很简单
【在 z*********8 的大作中提到】
: 我觉得是啊， coding很简单
s*u
117 楼
我自己小结的是，面试碰到：
1.prefix即波兰表达式，用递归最方便（因为操作符和操作数不是一种类型，操作符也
没有一种对应的文件类型，所以把操作符push进stack稍微麻烦点）；
2.postfix即逆波兰表达式，用stack最方便（因为总是先碰到操作数，不用push操作符
）。
3.infix即中缀表达式，不要求括号的话用longway大侠的方法，要求的话太麻烦了gg。
1.prefix即波兰表达式，用递归最方便（因为操作符和操作数不是一种类型，操作符也
没有一种对应的文件类型，所以把操作符push进stack稍微麻烦点）；
2.postfix即逆波兰表达式，用stack最方便（因为总是先碰到操作数，不用push操作符
）。
3.infix即中缀表达式，不要求括号的话用longway大侠的方法，要求的话太麻烦了gg。
r*7
118 楼
之前有个人 总结了 ebay 板上所有面经，其中就有这道题。 给出的解决方法就是
longway的那个。
楼主不好好刷题，可惜了。。 能说下是哪个组吗？
longway的那个。
楼主不好好刷题，可惜了。。 能说下是哪个组吗？
t*t
119 楼
这个是典型的编译原理的题。用计算表达式的方法做，其实不难。每个symbol要么是
operator，要么是operand。operator有优先级。看优先级决定入栈或出栈。
operator，要么是operand。operator有优先级。看优先级决定入栈或出栈。
s*u
120 楼
汗。。。首先，请看一下lz发帖的时间；其次，那个总结是我写的，然后解决方法就是
贴了longway的这个。。。所以前因后果反了哈哈
【在 r********7 的大作中提到】
: 之前有个人 总结了 ebay 板上所有面经，其中就有这道题。 给出的解决方法就是
: longway的那个。
: 楼主不好好刷题，可惜了。。 能说下是哪个组吗？
贴了longway的这个。。。所以前因后果反了哈哈
【在 r********7 的大作中提到】
: 之前有个人 总结了 ebay 板上所有面经，其中就有这道题。 给出的解决方法就是
: longway的那个。
: 楼主不好好刷题，可惜了。。 能说下是哪个组吗？
s*x
121 楼
刚刚试了一下，感觉还可以哈
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
r*7
122 楼
晕，那这帖子 怎么现在被顶到这么靠前了呢？ 我的错。。
【在 s********u 的大作中提到】
: 汗。。。首先，请看一下lz发帖的时间；其次，那个总结是我写的，然后解决方法就是
: 贴了longway的这个。。。所以前因后果反了哈哈
【在 s********u 的大作中提到】
: 汗。。。首先，请看一下lz发帖的时间；其次，那个总结是我写的，然后解决方法就是
: 贴了longway的这个。。。所以前因后果反了哈哈
m*c
123 楼
这个写的真的很好啊！
【在 l*********8 的大作中提到】
: 谢谢！ 这道题目， 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
: 面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
【在 l*********8 的大作中提到】
: 谢谢！ 这道题目， 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
: 面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
相关阅读
Amazon选组昨天，今天请问FB code题目网投G onsite后HR要求refer，跪求！跪求F家内推小弟求问LinkedIn那道Deep Iterator的题家庭主妇真诚寻求建议，谢谢大家H1B提交opt自动延期走过路过不要错过,感恩节大牛给建议:有人知道Abecco这个公司嘛?Yahoo 邮箱越做越烂了?!Ginobili 封 zoolbs 在 JobHunting 版 (转载)水果家的Test Stability QA位置，会面些什么在IBM工作的说说怎样才能进IBM提供 yahoo 内推趁人气问启蒙编程教材转行还是继续？站在人生的十字路口，求建议！湾区不好，也没见你离开该不该等到升级后再换工作呢？interviewer的名单下来了，6个interviewer里面5个老印关于原单位留你要不要留的问题, 答案只有一个.