j**7
发帖数: 143 | 1 第三题的答案：
public class InfixToPostfix {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
String infix="4*((5+6)*7";
infix="3+(1*2)";
String postfix=toPostfix(infix);
System.out.println(postfix);
System.out.println(evaluate(postfix));
}
//evaluate a postfix equation
static int evaluate(String postfix)
{
Stack st=new Stack阅读全帖 |
|
x****a
发帖数: 1229 | 2 在新建的stack中，调用generic method
public E remove（）方法出错。如果把E改成char，运行成功。请解惑。谢谢
/**********************************************************************
作业是实现infix， postfix互换，读取string input，把数字push to a stack，遇到
括号再pop。
要求stack必须用doublyLinkedList形式生成，就是先建DoublyLinkedList class， 再
创建stack class： DoublyLinkedList stack = new DoublyLinkedList；再创
建新class 里有infix to postfix 和 postfix to infix两个method。
我两个method里，infix to postfix， 用stack1; postfix to infix
用stack2。
there i... 阅读全帖 |
|
E*****m
发帖数: 25615 | 3 原來不知道可以用括號，改了一下
ev(('-',XT,YT),Z):-!,ev(XT,X),ev(YT,Y), Z is X-Y.
ev(('+',XT,YT),Z):-!,ev(XT,X),ev(YT,Y), Z is X+Y.
ev(('*',XT,YT),Z):-!,ev(XT,X),ev(YT,Y), Z is X*Y.
ev(('/',XT,YT),Z):-!,ev(XT,X),ev(YT,Y), Y =\= 0, Z is X/Y.
ev(X, X).
term([X,Y], (Op1, X,Y), Ops):-member(Op1, Ops).
term([H|T], (Op1, H,YT), Ops):- member(Op1, Ops), term(T,YT,Ops).
term([X,Y|T], (Op1, (Op2, X,Y), YT), Ops):- member(Op1, Ops), member(Op2,
Ops),term(T,YT,Ops).
solve1(List, Target, Term):- permutation(List, L1), ter... 阅读全帖 |
|
s*******3
发帖数: 134 | 4 各位大牛好，经常在看amazon面经的时候发现他家貌似狠喜欢考：prefix postfix
infix算术表达式的求值。。。这个是用
stack来做么？还是？
就拿infix最简单的来说把，哪位能给个伪代码或者是code的链接也行。。。小弟感激
不尽！ |
|
g**u
发帖数: 583 | 5 今天刚面的Amazon，求祝福
面的题目如下：面的是5个人，第一个是HR， 就聊了些大概的问题，关于Amazon,有关
面试安排， 面试的语言和他们的工作流程之类，略无不表。后面面了4个engineer，把
记住的题目说一下。
每轮面试45 minutes， Interviewer will come to the office.
有个的题目是：如何找到bst中第二大的数；可以用in order visit,然后返回倒数第二
个，但是时间和空间都是O(n)；要求improve，一个方案是寻找最大值（right most
nodes),然后寻找bst中最后一个小于该node的节点（log n)，要求code实现第二个方法
；然后是要在hash table中实现一个function可以按照插入的顺序打印出来；接着是实
现linux下面的count words，用了2个whileloop分别处理当前指针在word中和word间的
空格，要求2种情况一起处理，写了一半没写完（缺少练习啊）
有一个题目是关于C++和Java中的内存分配的；然后问了关于3-tier(UI, middle-tier
... 阅读全帖 |
|
p**o
发帖数: 3409 | 6
You may define the precedence levels for operators. E.g.,
precedence = {
'(': 0, ')': 0,
'+': 1, '-': 1,
'*': 2, '/': 2, '//': 2, '%': 2,
'^': 3, '**': 3,
}
operators = set(precedence.iterkeys())
right_associative_ops = {'^', '**',}
def infix_to_postlist (infix):
""" Simplified Shunting-yard algorithm. E.g.,
30 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
<==> 30 + ((4 * 2) / ((1 - 5) ^ (2 ^ 3)))
<==> 30 4 2 * 1 5 - 2 3 ^ ^ / +
"""
postlist = []
opstack = ... 阅读全帖 |
|
y*c
发帖数: 904 | 7 好难。
Calculator 是不是实现 infix->postfix 然后从postfix evaluate? |
|
g**u
发帖数: 583 | 8
面试完了就想到其实我们需要的是一个从 infix expression-->postfix expression的
预处理，但是等到自己想到这一步的时候，这个时候就需要合适的数据结构来实现这种
转变，binary tree就可以了，但是那时候时间快没了... |
|
d********w
发帖数: 363 | 9 infix expression to prefix expression.
eg:
3 * x + ( 9 + y ) / 4 ->
(+ (* 3 x) (/ (+ 9 y) 4))
参考了网上的一个递归写法，总体挺简洁的，这个复杂度是多少, 有没有O(N)的解法么？
＃reduce 用来标注是否能计算数值
def parse(s, reduce):
for operator in ["+-", "*/"]:
depth = 0
for p in xrange(len(s) - 1, -1, -1):
if s[p] == ')': depth += 1
if s[p] == '(': depth -= 1
if not depth and s[p] in operator:
left = parse(s[:p], reduce)
right = parse(s[p+1:], reduce)
... 阅读全帖 |
|
i*****e
发帖数: 63 | 10 convert it to postfix(or prefix) first and then convert it back to infix?? |
|
r**********g
发帖数: 22734 | 11 trie 的话只能从头搜。想fancy一点，prefix, suffix, infix都搜的话用suffix tree
想再fancy点，模糊匹配的话用inverted document |
|
e****e
发帖数: 418 | 12 写了一个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( ... 阅读全帖 |
|
e****e
发帖数: 418 | 13 写了一个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( ... 阅读全帖 |
|
s********u
发帖数: 1109 | 14 我自己小结的是，面试碰到：
1.prefix即波兰表达式，用递归最方便（因为操作符和操作数不是一种类型，操作符也
没有一种对应的文件类型，所以把操作符push进stack稍微麻烦点）；
2.postfix即逆波兰表达式，用stack最方便（因为总是先碰到操作数，不用push操作符
）。
3.infix即中缀表达式，不要求括号的话用longway大侠的方法，要求的话太麻烦了gg。 |
|
j**7
发帖数: 143 | 15 第三题应该用stack把infix expression转换成一个postfix expression,然后用stack
计算postfix expression. |
|
j*****0
发帖数: 160 | 16 自我介绍一下先……某崽，美国某鸟不拉屎小学校念大三中，大二时半路出家读的CS从
此苦海无边回头是岸……
现在自然在火烧眉毛的找暑假实习╮(╯▽╰)╭
一个月前面的G家和A家，G家一周内就下了拒信。A家说好的一周回复我，结果一直杳无
音讯，面完两周后我发邮件给HR依然没人理我。我完全是相信被默拒了结果！居然让我
点面第三次……刚刚看到某位拿了A家offer的亲发的帖子心里感到好宽慰好幸糊啊~不
知道这次完了要不要去西雅图嗯。
电面面经在此，顺求RP求祝福。
-----------------
Amazon: Jan 29, 12pm PST - 2pm PST
就决定开始把自己卖给人才市场的之后一段时间买了两本基础级别的书，一本《
Cracking the code interview》还一本《Programming interview exposed》。然后面
之前俩小时临时上网查了历年真题啥的，于是自然就对着答案在那边看边写。（我都无
语了提前一个月约的面试结果还是面之前俩小时准备的）
今天下午三点到五点就一直在和亚马逊的人电面~总共俩人给我电话，每个人40分钟左
右。。。大概就是每... 阅读全帖 |
|
j********x
发帖数: 2330 | 17 PS1: 1. Merge sorted linked lists; 2. Iterative inorder traversal of
binary tree
PS2: 1. Inorder successor of binary search tree;
onsite: 1. infix expression evaluation of integers and + - * /; 2.
implement a system to route packets based on their priority; implement
associative container Map; 3. Given n nodes, each node has 2 blocking
functions: send(int to_id, int msg); recv(int from_id); each node has a
value; design a method to distribute the sum of all values on every node to
all nodes; 4. ... 阅读全帖 |
|
j********x
发帖数: 2330 | 18 PS1: 1. Merge sorted linked lists; 2. Iterative inorder traversal of
binary tree
PS2: 1. Inorder successor of binary search tree;
onsite: 1. infix expression evaluation of integers and + - * /; 2.
implement a system to route packets based on their priority; implement
associative container Map; 3. Given n nodes, each node has 2 blocking
functions: send(int to_id, int msg); recv(int from_id); each node has a
value; design a method to distribute the sum of all values on every node to
all nodes; 4. ... 阅读全帖 |
|
|
t********e
发帖数: 12 | 20 the benefit of postfix or reverse polish expression is that it's a no
brainer evaluation. i.e. when you see a operator, just do evaluation.
the order of operands is actually the same as infix expression.
so ab+c/ => (a+b) c/ => ((a+b)/c) |
|
o*********r
发帖数: 203 | 21 You need to:
1) convert it into post-fix expression by using stack, which will eliminate
any brackets ( ).
2) compute result using stack.
There are many resources available online about 'Infix to postfix expression
' algorithm.
|
|
s******e
发帖数: 128 | 22 Given a sequence, 3 + 4 * 5 * 6 + 3 + 7 + ... of single digits, + and *,
Evaluate it.
就是infix polish notation. 我想不出如果用 inorder recursive 或stack 怎么做。 |
|
y***n
发帖数: 1594 | 23 Infix 如何做？ 不要考虑先乘除，后加加减 |
|
c******n
发帖数: 4965 | 24 多谢
那个prefix polish notation expression evaluation 你怎么做的？
infix 超难， postfix 很简单， refix 看一眼觉得很难， 但con右边scan 基本跟
postfix 差不多
onsite |
|
f****e
发帖数: 923 | 25 亲身经历，candidate 是个烙印， 小印是面试官之一， 面完之后向烙印manager报告
，说出了2个题， 第一个是string infix 转 postfix， 只写了70%
第二个题是，print斐波那契数列，只写了递归，
小印人为这个candidate虽然第一题没写完，但是思路是对的，如果给予充足时间，写
不来没问题， 第二题完美解出来了， 所以总体coding非常不错
如果换成某些中国面试官， 第二题如果没写出o(1) space， o(n) time的 解法，基本
算你
废了 |
|
n******n
发帖数: 409 | 26 我面试从来不出题。基本看完简历就大概知道这个人合不合适了。然后就是聊天看看性
格，了解一下智商，是否好学不是是那种特别隔应的基本就行了。
[在 fcwrme (刷题转码,脱贫致富,奔小康) 的大作中提到：]
:亲身经历，candidate 是个烙印， 小印是面试官之一， 面完之后向烙印manager报告
:，说出了2个题， 第一个是string infix 转 postfix， 只写了70%
:第二个题是，print斐波那契数列，只写了递归，
:小印人为这个candidate虽然第一题没写完，但是思路是对的，如果给予充足时间，写
:不来没问题， 第二题完美解出来了， 所以总体coding非常不错
:如果换成某些中国面试官， 第二题如果没写出o(1) space， o(n) time的 解法，基
本算你
:废了 |
|
f****e
发帖数: 923 | 27 亲身经历，candidate 是个烙印， 小印是面试官之一， 面完之后向烙印manager报告
，说出了2个题， 第一个是string infix 转 postfix， 只写了70%
第二个题是，print斐波那契数列，只写了递归，
小印人为这个candidate虽然第一题没写完，但是思路是对的，如果给予充足时间，写
不来没问题， 第二题完美解出来了， 所以总体coding非常不错
如果换成某些中国面试官， 第二题如果没写出o(1) space， o(n) time的 解法，基本
算你
废了 |
|
n******n
发帖数: 409 | 28 我面试从来不出题。基本看完简历就大概知道这个人合不合适了。然后就是聊天看看性
格，了解一下智商，是否好学不是是那种特别隔应的基本就行了。
[在 fcwrme (刷题转码,脱贫致富,奔小康) 的大作中提到：]
:亲身经历，candidate 是个烙印， 小印是面试官之一， 面完之后向烙印manager报告
:，说出了2个题， 第一个是string infix 转 postfix， 只写了70%
:第二个题是，print斐波那契数列，只写了递归，
:小印人为这个candidate虽然第一题没写完，但是思路是对的，如果给予充足时间，写
:不来没问题， 第二题完美解出来了， 所以总体coding非常不错
:如果换成某些中国面试官， 第二题如果没写出o(1) space， o(n) time的 解法，基
本算你
:废了 |
|
Y********6
发帖数: 28 | 29 【 以下文字转载自 Computation 讨论区 】
发信人: Yolanda886 (Yolanda886), 信区: Computation
标 题: 准备100个包子求大神帮下忙
发信站: BBS 未名空间站 (Tue Feb 26 10:02:58 2013, 美东)
马上去找人买100个包子，求哪位大神能赐教帮忙提点一下怎么写下面这个project，谢
谢啦
不好意思，学了几节课又不知道怎么入手了。。想了一周实在不知道怎么写出来，不知
道怎么一个个调取然后分析，感觉很多变量和变化情况，直接写code好像太复杂了
题目是
In reverse Polish notation the operators follow their operands;
To add 3 and 4, one would write "3 4 +" rather than "3 + 4".
If there are multiple operations, the operator is given immediately after
its second operand
The expressi... 阅读全帖 |
|
x****a
发帖数: 1229 | 30 // public void postfix (String input)
// {
// Stack s1 = new Stack();
// String output = "";//to store the postfix expression
//
// for (int i =0; i
// {
// //get the single letter
// char letter = input.charAt(i);
//
// //convert infix to postfix
// if (letter =='1'||letter =='2'|| letter =='3'||letter =='4'||
letter =='5'||letter =='6'||
// letter =='7'||le... 阅读全帖 |
|
w*********n
发帖数: 439 | 31 A calculator application that allows prefix, infix, and postfix expressions
to be evaluated (i.e., allows all 3 types of expressions).
List
Queue
Deque
Binary tree
Binary search tree
B tree
HashMap
HashSet
Priority Queue
Graph |
|
r*********r
发帖数: 3195 | 32 scheme/lisp 的语法其实是最简单的, 只有 function calling.
(foo x y) 就相当于 c 里的 foo(x,y)
难看懂是因为没有 c 里的 infix 的 operator, 所以 x+y/z 要写成 (+ x (/ y z)). |
|
n******n
发帖数: 12088 | 33 其实infix没有任何优点，就是个习惯。如果从小教育post or pre fix，大家也不会觉
得有什么。
). |
|
G****A
发帖数: 4160 | 34 need it in c++. any thoughts? |
|
g*********s
发帖数: 1782 | 35 homework? find a compiler text book. usually a typical example. |
|
|
g*********s
发帖数: 1782 | 37 E ::= T | T + E
T ::= F | F * T
F ::= | ( E )
sth like that. |
|
E*****m
发帖数: 25615 | 38
看了一下， 語法不太好。
比方
(define swap
{(A * B) --> (B * A)}
(@p X Y) -> (@p Y X))
既然是 Lisp, 為啥 --> 和 -> 是 infix 呢？ 這樣 macro 不是很難寫嗎？
什麼都抄一點， 太亂了。 |
|
l**********n
发帖数: 8443 | 39 scala code is a mixture of postfix, infix and prefix code. it is really hard
to read. even an function is an object. so you don't know whether it is a
function or an object.
you can write + X Y or X + Y or X Y +. |
|
x***4
发帖数: 1815 | 40 我的愿望：出一个scala lite
没有implicit conversion，implicit parameter。
精简现在的符号。::和++和+:都可以表示list的concat这样的情况要消失。
._1解tuple要禁止。
禁infix notation（这个可能不现实）
Protected 和private跟java的convention.
Etc
基本原则就是explicit，避免同一样事情有n种做法。 |
|
Y********6
发帖数: 28 | 41 马上去找人买100个包子，求哪位大神能赐教帮忙提点一下怎么写下面这个project，谢
谢啦
不好意思，学了几节课又不知道怎么入手了。。想了一周实在不知道怎么写出来，不知
道怎么一个个调取然后分析，感觉很多变量和变化情况，直接写code好像太复杂了
题目是
In reverse Polish notation the operators follow their operands;
To add 3 and 4, one would write "3 4 +" rather than "3 + 4".
If there are multiple operations, the operator is given immediately after
its second operand
The expression written "3 − 4 + 5” would be written "3 4 − 5 +"
in RPN: first subtract 4 from 3, then add 5 to that
An advantage of RPN is th... 阅读全帖 |
|
z*******n
发帖数: 1034 | 42 来自主题: MobileDevelopment版 - Swift 出现了个func，既不是个word也不是众所周知的abbreviation
Keywords and Punctuation
The following keywords are reserved and can’t be used as identifiers,
unless they’re escaped with backticks, as described above in Identifiers.
Keywords other than inout, var, and let can be used as external parameter
names in a function declaration or function call without being escaped with
backticks.
Keywords used in declarations: associatedtype, class, deinit, enum,
extension, func, import, init, inout, internal, let, operator, p... 阅读全帖 |
|
