还热乎的google电面

jbzhang 发表于 2019/02/28 09:34:34


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

就按照DFS的思路写，只要碰到括号，就递归到括号里面去，返回的是这个括号算出来的值。

Thanks, you are the best!

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

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

请问楼主 这数字还会有负数？请问咋处理负数。。

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

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.     }  

复制代码