Redian新闻
>
Ebay二电面,铁挂了,这回求安慰吧。。。
avatar
Ebay二电面,铁挂了,这回求安慰吧。。。# JobHunting - 待字闺中
g*i
1
成交量低,成交价也低。咳,历史新低啊。
avatar
f*7
2
题目一出,我就傻眼了,就知道完蛋了。。。
这题目正好是隔壁BB Onsite面经第二题
给一个表达式,计算返回值,不带括号
例子
"7-12/6"
"1000-5*6/3*2+1"
写了半天,问对方,对吗? 多方说,你说呢。。。
祝大家好运吧,哪个大牛给个链接
avatar
c*a
3
成交量为0的飘过。。。
avatar
p*2
4
看了一下。这题你怎么做的?
感觉扫两遍就可以了吧?第一遍算乘除,第二遍算加减。
avatar
b*j
5
是吗?今天我成交量是礼拜一到礼拜五的总和啊。

【在 g*****i 的大作中提到】
: 成交量低,成交价也低。咳,历史新低啊。
avatar
a*o
6
stack就行了,或者搞个temp variable

【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的?
: 感觉扫两遍就可以了吧?第一遍算乘除,第二遍算加减。

avatar
f*n
7
偶这一两天也是啥客人都没有。
avatar
h*0
8
2爷您的想法和我之前onsite BB的想法一样。。 结果面试官压根不屌我。 必须用
recursive。 我说recursive不好,被华丽丽的鄙视了。。。

【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的?
: 感觉扫两遍就可以了吧?第一遍算乘除,第二遍算加减。

avatar
R*g
9
我也是0
avatar
p*2
10

stack更简单吗?

【在 a***o 的大作中提到】
: stack就行了,或者搞个temp variable
avatar
l*n
11
套套和情趣用品出外...
看来是接了石头阿姨的班

【在 b**j 的大作中提到】
: 是吗?今天我成交量是礼拜一到礼拜五的总和啊。
avatar
p*2
12

recursive怎么搞呀?

【在 h*******0 的大作中提到】
: 2爷您的想法和我之前onsite BB的想法一样。。 结果面试官压根不屌我。 必须用
: recursive。 我说recursive不好,被华丽丽的鄙视了。。。

avatar
b*j
13
明天就情人节了今天order,礼拜六,明天怎么deliver啊。呵呵

【在 l******n 的大作中提到】
: 套套和情趣用品出外...
: 看来是接了石头阿姨的班

avatar
f*7
14
二爷这题我没见过,硬着头皮写recursive,思路都不对,今天就问了这一题。。。
有相关讲解的链接吗?

【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的?
: 感觉扫两遍就可以了吧?第一遍算乘除,第二遍算加减。

avatar
l*n
15
都是overnight呀
BSO shipping都赚疯了

【在 b**j 的大作中提到】
: 明天就情人节了今天order,礼拜六,明天怎么deliver啊。呵呵
avatar
h*0
16
我当时也没想出来。 然后我和他说,我这个方法比recursive好。。 我说recursive可
能会out of memory。 人家根本不同意我的说法。

【在 p*****2 的大作中提到】
:
: recursive怎么搞呀?

avatar
h*0
17
我觉得如果见到没见过的题就要赶紧研究。。 弄不好就是你下一道题。。 这题其实挺
不好写的

【在 f*******7 的大作中提到】
: 题目一出,我就傻眼了,就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式,计算返回值,不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接

avatar
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,思路都不对,今天就问了这一题。。。
: 有相关讲解的链接吗?

avatar
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
: 第二遍算加减就从头算到尾就可以了
: 想想有没有什么更简单的办法。

avatar
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;
}
avatar
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)
avatar
h*8
22
尝试构造一个对应的AST?不知道可不可以
avatar
p*2
23

应该可以。就是写起来不知道是不是容易bug free。你可以写写看看。

【在 a***o 的大作中提到】
: 搞俩variable就行了,一个存之前的数,
: 一个存当前的数,碰到乘除,更新当前的数,碰到加减更新之前的数

avatar
o*d
24
我记得这个是我在国内尚数据结构时stack的李子(当然可能各个学校不一样),参考严蔚
敏的书

【在 f*******7 的大作中提到】
: 题目一出,我就傻眼了,就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式,计算返回值,不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接

avatar
o*d
25
另外,这个我在careercup上见过google也考过似乎

【在 o***d 的大作中提到】
: 我记得这个是我在国内尚数据结构时stack的李子(当然可能各个学校不一样),参考严蔚
: 敏的书

avatar
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;
}
avatar
m*1
27
电面考这个,要求有点高啊,写计算器是以前学做编译原理搞语法和词法分析的小
project哎
avatar
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]*
avatar
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"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接

avatar
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)
}
avatar
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

avatar
q*s
32
这个不是逆波兰吗?

★ 发自iPhone App: ChineseWeb 7.8

【在 f*******7 的大作中提到】
: 题目一出,我就傻眼了,就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式,计算返回值,不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接

avatar
a*o
33
写的漂亮,可能C比较简洁

【在 h*******0 的大作中提到】
: 为啥感觉你代码写的这么优美呢? 难道是排版排的好? :)
avatar
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 );
}
avatar
w*x
35

可能因为我比较帅吧

【在 h*******0 的大作中提到】
: 为啥感觉你代码写的这么优美呢? 难道是排版排的好? :)
avatar
l*a
36
看linkedin不像啊

【在 w****x 的大作中提到】
:
: 可能因为我比较帅吧

avatar
w*x
37

等等,我马上换成刘德华的

【在 l*****a 的大作中提到】
: 看linkedin不像啊
avatar
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;
}
avatar
x*6
39
先把表达式转换成operand和operator的string[],再转换成postfix notation,最后用
一个stack来帮助计算
avatar
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

avatar
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);
}
avatar
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;

avatar
l*b
44
学习了...发愁那个减号怎么处理呢...原来是sscanf...哈哈

【在 l*********8 的大作中提到】
: 测试案例:
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595

avatar
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));
}
}
}
avatar
M*l
46
逆波兰表达式吧?用个stack就行了,两年前面试被问过,当时居然正好复习到了~~
http://baike.baidu.com/view/552648.htm

【在 f*******7 的大作中提到】
: 题目一出,我就傻眼了,就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式,计算返回值,不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接

avatar
p*2
48

longway又出手了。

【在 l*********8 的大作中提到】
: 测试案例:
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595

avatar
H*s
49
还是这个牛啊!

【在 l*********8 的大作中提到】
: 测试案例:
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595

avatar
p*2
50

longway的代码向来都是最简洁的。

【在 H****s 的大作中提到】
: 还是这个牛啊!
avatar
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

avatar
p*2
52

这东西没搞过。回头看看。

【在 e****e 的大作中提到】
: 写了一个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() )

avatar
l*8
53
谢谢! 这道题目, 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
面经,面试官似乎是把题目简化了,并期望一个简单些的解答。

【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。

avatar
d*f
54
20年前你这么回答可能还行

【在 h*******0 的大作中提到】
: 我当时也没想出来。 然后我和他说,我这个方法比recursive好。。 我说recursive可
: 能会out of memory。 人家根本不同意我的说法。

avatar
n*e
55
哈哈,这个牛!居然能这么处理。

【在 l*********8 的大作中提到】
: 谢谢! 这道题目, 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
: 面经,面试官似乎是把题目简化了,并期望一个简单些的解答。

avatar
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;
}
avatar
I*s
57
三个主要函数: getNextToken(), buildAST(), eval(). buildAST() 可以是iteration
, eval()是recursion.
avatar
y*x
58
写了个JavaScript的,想法跟二爷一开始的一样,扫两遍,一遍处理+-, 一遍处理*/
function getnum(str){
var n = str.split(/[+\-]+/);
var c = str.split(/[0-9\*\/]+/);

for(var i=0; in[i] = getmdnum(n[i]);
}

for(var j=0; jn[j+1] = cal(n[j], n[j+1], c[j+1]);
}

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; in[i+1] = cal(n[i], n[i+1], c[i+1]);
}

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";
}
}
avatar
f*7
60
题目一出,我就傻眼了,就知道完蛋了。。。
这题目正好是隔壁BB Onsite面经第二题
给一个表达式,计算返回值,不带括号
例子
"7-12/6"
"1000-5*6/3*2+1"
写了半天,问对方,对吗? 多方说,你说呢。。。
祝大家好运吧,哪个大牛给个链接
avatar
p*2
61
看了一下。这题你怎么做的?
感觉扫两遍就可以了吧?第一遍算乘除,第二遍算加减。
avatar
a*o
62
stack就行了,或者搞个temp variable

【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的?
: 感觉扫两遍就可以了吧?第一遍算乘除,第二遍算加减。

avatar
h*0
63
2爷您的想法和我之前onsite BB的想法一样。。 结果面试官压根不屌我。 必须用
recursive。 我说recursive不好,被华丽丽的鄙视了。。。

【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的?
: 感觉扫两遍就可以了吧?第一遍算乘除,第二遍算加减。

avatar
p*2
64

stack更简单吗?

【在 a***o 的大作中提到】
: stack就行了,或者搞个temp variable
avatar
p*2
65

recursive怎么搞呀?

【在 h*******0 的大作中提到】
: 2爷您的想法和我之前onsite BB的想法一样。。 结果面试官压根不屌我。 必须用
: recursive。 我说recursive不好,被华丽丽的鄙视了。。。

avatar
f*7
66
二爷这题我没见过,硬着头皮写recursive,思路都不对,今天就问了这一题。。。
有相关讲解的链接吗?

【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的?
: 感觉扫两遍就可以了吧?第一遍算乘除,第二遍算加减。

avatar
h*0
67
我当时也没想出来。 然后我和他说,我这个方法比recursive好。。 我说recursive可
能会out of memory。 人家根本不同意我的说法。

【在 p*****2 的大作中提到】
:
: recursive怎么搞呀?

avatar
h*0
68
我觉得如果见到没见过的题就要赶紧研究。。 弄不好就是你下一道题。。 这题其实挺
不好写的

【在 f*******7 的大作中提到】
: 题目一出,我就傻眼了,就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式,计算返回值,不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接

avatar
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,思路都不对,今天就问了这一题。。。
: 有相关讲解的链接吗?

avatar
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
: 第二遍算加减就从头算到尾就可以了
: 想想有没有什么更简单的办法。

avatar
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;
}
avatar
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)
avatar
h*8
73
尝试构造一个对应的AST?不知道可不可以
avatar
p*2
74

应该可以。就是写起来不知道是不是容易bug free。你可以写写看看。

【在 a***o 的大作中提到】
: 搞俩variable就行了,一个存之前的数,
: 一个存当前的数,碰到乘除,更新当前的数,碰到加减更新之前的数

avatar
o*d
75
我记得这个是我在国内尚数据结构时stack的李子(当然可能各个学校不一样),参考严蔚
敏的书

【在 f*******7 的大作中提到】
: 题目一出,我就傻眼了,就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式,计算返回值,不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接

avatar
o*d
76
另外,这个我在careercup上见过google也考过似乎

【在 o***d 的大作中提到】
: 我记得这个是我在国内尚数据结构时stack的李子(当然可能各个学校不一样),参考严蔚
: 敏的书

avatar
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;
}
avatar
m*1
78
电面考这个,要求有点高啊,写计算器是以前学做编译原理搞语法和词法分析的小
project哎
avatar
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]*
avatar
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"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接

avatar
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)
}
avatar
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

avatar
q*s
83
这个不是逆波兰吗?

★ 发自iPhone App: ChineseWeb 7.8

【在 f*******7 的大作中提到】
: 题目一出,我就傻眼了,就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式,计算返回值,不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接

avatar
a*o
84
写的漂亮,可能C比较简洁

【在 h*******0 的大作中提到】
: 为啥感觉你代码写的这么优美呢? 难道是排版排的好? :)
avatar
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 );
}
avatar
w*x
86

可能因为我比较帅吧

【在 h*******0 的大作中提到】
: 为啥感觉你代码写的这么优美呢? 难道是排版排的好? :)
avatar
l*a
87
看linkedin不像啊

【在 w****x 的大作中提到】
:
: 可能因为我比较帅吧

avatar
w*x
88

等等,我马上换成刘德华的

【在 l*****a 的大作中提到】
: 看linkedin不像啊
avatar
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;
}
avatar
x*6
90
先把表达式转换成operand和operator的string[],再转换成postfix notation,最后用
一个stack来帮助计算
avatar
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

avatar
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);
}
avatar
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;

avatar
l*b
95
学习了...发愁那个减号怎么处理呢...原来是sscanf...哈哈

【在 l*********8 的大作中提到】
: 测试案例:
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595

avatar
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));
}
}
}
avatar
M*l
97
逆波兰表达式吧?用个stack就行了,两年前面试被问过,当时居然正好复习到了~~
http://baike.baidu.com/view/552648.htm

【在 f*******7 的大作中提到】
: 题目一出,我就傻眼了,就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式,计算返回值,不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接

avatar
p*2
99

longway又出手了。

【在 l*********8 的大作中提到】
: 测试案例:
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595

avatar
H*s
100
还是这个牛啊!

【在 l*********8 的大作中提到】
: 测试案例:
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595

avatar
p*2
101

longway的代码向来都是最简洁的。

【在 H****s 的大作中提到】
: 还是这个牛啊!
avatar
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

avatar
p*2
103

这东西没搞过。回头看看。

【在 e****e 的大作中提到】
: 写了一个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() )

avatar
l*8
104
谢谢! 这道题目, 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
面经,面试官似乎是把题目简化了,并期望一个简单些的解答。

【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。

avatar
d*f
105
20年前你这么回答可能还行

【在 h*******0 的大作中提到】
: 我当时也没想出来。 然后我和他说,我这个方法比recursive好。。 我说recursive可
: 能会out of memory。 人家根本不同意我的说法。

avatar
n*e
106
哈哈,这个牛!居然能这么处理。

【在 l*********8 的大作中提到】
: 谢谢! 这道题目, 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
: 面经,面试官似乎是把题目简化了,并期望一个简单些的解答。

avatar
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;
}
avatar
I*s
108
三个主要函数: getNextToken(), buildAST(), eval(). buildAST() 可以是iteration
, eval()是recursion.
avatar
y*x
109
写了个JavaScript的,想法跟二爷一开始的一样,扫两遍,一遍处理+-, 一遍处理*/
function getnum(str){
var n = str.split(/[+\-]+/);
var c = str.split(/[0-9\*\/]+/);

for(var i=0; in[i] = getmdnum(n[i]);
}

for(var j=0; jn[j+1] = cal(n[j], n[j+1], c[j+1]);
}

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; in[i+1] = cal(n[i], n[i+1], c[i+1]);
}

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";
}
}
avatar
d*r
111
先转换成postfix再用stack来实现就容易很多吧。
avatar
u*o
112
mark一下,赶脚这楼里出手的大牛们很多呀
avatar
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;

avatar
z*8
114
我觉得是啊, coding很简单

【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。

avatar
V*r
115
>>> s = "1000-5*6/3*2+1"
>>> eval(s)
981
avatar
s*u
116
stack 用来做postfix简单,prefix要用两个或者倒序遍历字符串。没看出写中缀用
stack很简单

【在 z*********8 的大作中提到】
: 我觉得是啊, coding很简单
avatar
s*u
117
我自己小结的是,面试碰到:
1.prefix即波兰表达式,用递归最方便(因为操作符和操作数不是一种类型,操作符也
没有一种对应的文件类型,所以把操作符push进stack稍微麻烦点);
2.postfix即逆波兰表达式,用stack最方便(因为总是先碰到操作数,不用push操作符
)。
3.infix即中缀表达式,不要求括号的话用longway大侠的方法,要求的话太麻烦了gg。
avatar
r*7
118
之前有个人 总结了 ebay 板上所有面经,其中就有这道题。 给出的解决方法就是
longway的那个。
楼主不好好刷题,可惜了。。 能说下是哪个组吗?
avatar
t*t
119
这个是典型的编译原理的题。用计算表达式的方法做,其实不难。每个symbol要么是
operator,要么是operand。operator有优先级。看优先级决定入栈或出栈。
avatar
s*u
120
汗。。。首先,请看一下lz发帖的时间;其次,那个总结是我写的,然后解决方法就是
贴了longway的这个。。。所以前因后果反了哈哈

【在 r********7 的大作中提到】
: 之前有个人 总结了 ebay 板上所有面经,其中就有这道题。 给出的解决方法就是
: longway的那个。
: 楼主不好好刷题,可惜了。。 能说下是哪个组吗?

avatar
s*x
121
刚刚试了一下,感觉还可以哈

【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。

avatar
r*7
122
晕,那这帖子 怎么现在被顶到这么靠前了呢? 我的错。。

【在 s********u 的大作中提到】
: 汗。。。首先,请看一下lz发帖的时间;其次,那个总结是我写的,然后解决方法就是
: 贴了longway的这个。。。所以前因后果反了哈哈

avatar
m*c
123
这个写的真的很好啊!

【在 l*********8 的大作中提到】
: 谢谢! 这道题目, 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
: 面经,面试官似乎是把题目简化了,并期望一个简单些的解答。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。