还热乎的google电面

朋友内推，刷题还没准备太多。

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

写了一下 假设没有负数的话 大概这样 请指点

1. public static void main(String[] args) {
   
2.         System.out.println(Sexpression("(* (* 6(+ 5 8 6))(+ 9 ( * 2 2 )))"));
   
3.         //(* (* 6(+ 5 8 6))(+ 9 ( * 2 2 )))
   
4.     }
   
5.     public static int Sexpression(String s){
   
6.      Queue<Character> queue = new LinkedList<>();
   
7.         for(char c : s.toCharArray()){
   
8.             //if(c != ' '){
   
9.                 queue.offer(c);
   
10.             //}
    
11.         }
    
12.         //queue.offer('+');
    
13.         return helper(queue);
    
14.     }
    
15.     public static int helper(Queue<Character> q){
    
16.         int res = 0;
    
17.         int num = 0;
    
18.         Stack<Integer> stack = new Stack<>();
    
19.         Stack<Character> sstack = new Stack<>();
    
20.         //sstack.push('+');
    
21.         while(!q.isEmpty()){
    
22.             char c = q.poll();
    
23.             if(Character.isDigit(c)){
    
24.                 num = num * 10 + (c-'0');
    
25.                 System.out.println(num);
    
26.                 while(!q.isEmpty() && Character.isDigit(q.peek())){
    
27.                     char tmp = q.poll();
    
28.                     System.out.println(tmp);
    
29.                     num = num * 10 + (tmp-'0');
    
30.                 }
    
31.                 stack.push(num);
    
32.                 num = 0;
    
33.             }else if(c == '(') {
    
34.                 stack.push(helper(q));
    
35.             }else if(c == ' '){
    
36.                
    
37.                 continue;
    
38.             }else{
    
39.                 if(c == '+' || c == '-' || c == '*' || c =='/'){
    
40.                     //System.out.println(c);
    
41.                     sstack.push(c);
    
42.                 }
    
43.                 num=0;
    
44.                 if(c == ')'){
    
45.                     break;
    
46.                 }
    
47.             }
    
48.         }
    
49.         if(sstack.isEmpty())return res;
    
50.         char sign = sstack.pop();
    
51.         System.out.println(sign);
    
52.         if(stack.isEmpty())return res;
    
53.         if(sign == '*')res = 1;
    
54.         for(int s : stack){
    
55.             if(sign == '+'){
    
56.                 res += s;
    
57.             }else if(sign == '-'){
    
58.                 res -= s;
    
59.             }else if(sign == '*'){
    
60.                 res *= s;
    
61.             }else if(sign == '/'){
    
62.                 res /= s;
    
63.             }         
    
64.         }
    
65.         System.out.println(res);
    
66.         return res;
    
67.     }  

复制代码

iq136man 发表于 2019-2-28 08:03
楼主能讲讲你的思路吗？ 碰到这种题我脑子就有坑。。。
已加米。

就是一个个加进一个stack，碰到一个“）”，就pop，直到有“（”pop出来，利用pop的operator求解，加入stack
然后继续，直到最后一个（被pop，得到最终解

pandami 发表于 2019-2-28 05:38
哦 一个符号可以负责后面所有的数字啊
和波兰表达式还不太一样
+ + 5 8 6

这个应该是S-expression，不是polish expression

+ 5 8 6变成 13 6之后怎么办？是不是少了一个符号？

pandami 发表于 2019-2-28 05:18
+ 5 8 6变成 13 6之后怎么办？是不是少了一个符号？

+ 5 8 6 的结果应该是19. 计算括号里面的

jbzhang 发表于 2019/02/28 05:33:58


+ 5 8 6 的结果应该是19. 计算括号里面的

哦 一个符号可以负责后面所有的数字啊
和波兰表达式还不太一样
+ + 5 8 6

我的天，和普通思维的数学表达式好容易搞混

楼主能讲讲你的思路吗？ 碰到这种题我脑子就有坑。。。
已加米。

楼主，stack实现不好写可以考虑写递归版本啊，代码应该看起来更简单些。

同楼上，这个问题用递归写更好写，因为一个operator对应不止两个数

pengdu 发表于 2019-2-28 08:10
楼主，stack实现不好写可以考虑写递归版本啊，代码应该看起来更简单些。

递归版本我还真不会，求指教