D****6
发帖数: 278 | 1 input: * + 2 3 4
output: 20
今天电面挂这儿了。这题recursion怎么做？ | x********0
发帖数: 94 | 2 当年在电脑上写的面试题啊 好怀念
非recursion:
不停地找‘operation number number’ 的组合
recursion
类似的方法，不过找number的时候tricky一点。建立两个counter，一个数operator的
数量，一个数number的数量。当number的数量=operator+1，就可以切出来成为一个
number | r********7
发帖数: 102 | 3 用stack， 一个stack放数字 一个stack放符号。
如果数字那个stack size 达到2， 怎pop这两个数字 并且pop一个符号 进行运算。 得
到的值再放进数字的stack。
继续读数。
直到读完input 并且符号stack为空， return 数字stack pop的元素 | r********7
发帖数: 102 | 4 也可以这样 从后往前， 只需要一个stack， 先存 4， 再存3， 再存2. 遇到符号 则
pop两次。 然后和符号运算。 结果在放进stack 然后继续，直到没有输入。
wiki：
http://en.wikipedia.org/wiki/Polish_notation | u*****o
发帖数: 1224 | 5 这题recursion比非recursion难写啊。。 | L*******e
发帖数: 114 | 6 Recursive solution: 两头切不行吗？ | c**1
发帖数: 71 | 7 int reverse_polish(const char*& str) {
OpCode op = getOpCode(str);
int x = reverse_polish(str);
int y = reverse_polish(str);
return op.apply(x,y);
} | r********7
发帖数: 102 | 8 始终没想到 recursion， 求大神上code。。。 | s***5
发帖数: 2136 | 9 从末尾开始找第一个operator，找到就把之后的两个数取出做运算，把结果放回原
string，再接着recusion。 | c**1
发帖数: 71 | 10 here is the correct version:
int reverse_polish(const char*& str) {
if (is_number(str)) return parse_nuber(str);
OpCode op = getOpCode(str);
int x = reverse_polish(str);
int y = reverse_polish(str);
return op.apply(x,y);
}
note there is no error check, and note str is passed as reference to const
char*, so that functions can read what it needs as well as forwarding the
pointer. | r********7
发帖数: 102 | 11 有没有java的实现方法啊，不太看得懂这个。。。
【在 x********0 的大作中提到】
: 当年在电脑上写的面试题啊 好怀念
: 非recursion:
: 不停地找‘operation number number’ 的组合
: recursion
: 类似的方法，不过找number的时候tricky一点。建立两个counter，一个数operator的
: 数量，一个数number的数量。当number的数量=operator+1，就可以切出来成为一个
: number
| f*******b
发帖数: 520 | | L*******e
发帖数: 114 | 13 试着用Java写了一个。还是不够简练。Have to use String array, otherwise cannot
push the result back to the original array.
public static int evaluate(String[] array, int from, int to){
// get first operator, backward
int j = to;
String s = array[j];
while (j >= from && !Operator.isOperator(s.charAt(0))){
s = array[--j];
}
// get operands
Operator op = Operator.getOperator(s.charAt(0));
int opIndex = j;
int a = Integer.valueOf(array[++j]);
int b = Integer.valueOf(array[++j]);
int result = op.apply(a, b);
// most-left operator, done
if (opIndex == 0){
return result;
}
// push result back
array[opIndex] = Integer.toString(result);
//copy remaining over
j++;
while (j <= to){
array[++opIndex]= array[j++];
}
return evaluate(array, from, opIndex);
}
@Test
public void testPolishNotationSimple(){
String[] array = {"-", "5", "*", "6", "7"};
int result = PolishNotation.evaluate(array, 0, array.length - 1);
assertEquals(result, -37);
}
@Test
public void testPolishNotationSimple2(){
String[] array = {"*", "+", "2", "3", "4"};
int result = PolishNotation.evaluate(array, 0, array.length - 1);
assertEquals(result, 20);
}
@Test
public void testPolishNotationComplex(){
String[] array = {"-", "*", "/", "15", "-", "7", "+", "1", "1", "3", "+"
, "2", "+", "1", "1"};
int result = PolishNotation.evaluate(array, 0, array.length - 1);
assertEquals(result, 5);
} |
|
