资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/【LintCode】Expression Expand 非递归stack完成DFS（String）

【LintCode】Expression Expand 非递归stack完成DFS（String）

livem / 1732人阅读

摘要：直接的方法不可取因为是每一层。层直接从取出实际上是将这个后应该得到。这个时候考虑逆向，建立一个，将出来的东西再一个顺序，逆逆得顺是一个很好用的操作符，判断一个对象是否是一个类的实例。坑小心一点这种情况啊代码

这道题真是超级棒的stack DFS样板题啊，在这里给自己写个小小的总结

思路：
想到stack并不难，这种嵌套式一般是DFS的思想，先走到最里面最小的那个括号，然后逐渐回到上一层→上一层。又∵非递归，“BFS queue， DFS stack”。想到用stack并不难
Stack non-recursion DFS template
要点是，处理完之后重新返回stack，才能够回到上一层操作

这个题具体操作起来真是很多可圈可点的地方，主要是在于String的处理上

reverse
因为stack的顺序，在这个题中需要每次将每层里的内容reverse。直接StringBuilder的reverse方法不可取：因为是reverse每一层。e.g. 3[ab]2[c]层直接从stack取出实际上是cc, ababab将这个reverse后应该得到abababcc。这个时候考虑逆向stack，建立一个stack buffer，将stack pop出来的东西再reverse一个顺序，逆逆得顺

instanceof
nstanceof是一个很好用的操作符，a instanceof A,判断“一个对象是否是一个类的实例”。作为操作符instanceof不可以直接在最前面！取非（比如>=这种也是），而是用 a instanceof A == false之类的判断

复制StringBuilder
add到底append几次，怎么append：直接append add 是不可以的，因为add是在变的，必须要先将第一个add保存起来，类似于dummy node，预先保存queue size这种“锚定”。

坑
小心一点0[peer], -3[aaa]这种情况啊！

代码
public class Solution {

public String expressionExpand(String s) {
    Stack stack = new Stack<>();
    char[] arr = s.toCharArray();
    
    int num = 0;
    for(char c : arr){
       if(Character.isDigit(c)){
           num = num * 10 + c - "0";
       }
       else if(c == "["){
           stack.push(Integer.valueOf(num));
           num = 0;
       }
       else if(c == "]"){
           popStack(stack);
       }
       else{
           stack.push(c);
       }
    }
    popStack(stack);
    return stack.pop().toString();
}
private void popStack(Stack stack){
    StringBuilder add = new StringBuilder();
    int count;
    Stack buffer = new Stack();
    while(!stack.isEmpty() && stack.peek() instanceof Integer == false){
        buffer.push(stack.pop());
    }
    while(!buffer.isEmpty()){
        add.append(buffer.pop());
    }
    
    count = stack.isEmpty()? 1 : (Integer) stack.pop();
    StringBuilder part = new StringBuilder(add);
    if(count > 0){
        for(int i = 0; i < count - 1; i++)
            add.append(part);
        stack.push(add);// reput
    }
}

}
           
               
                                           
                       
                 
            
                     

                 

                                                                                                                    
                         GPU云服务器
                                             
                         云服务器
                                                                                                                                                 
                                      
                     
                    
                                                                                               非递归遍历
                                                                                                           非递归先序
                                                                                                           非递归二叉树遍历
                                                                                                           Expand
                                                         
                 

               
              

             
               

                   
 文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

                 
                   
转载请注明本文地址：https://www.ucloud.cn/yun/66920.html

               

                      
               
              
              

                
相关文章

                
    
                             
                                                                                                    
  • 
                                                
    
                          
    [LintCode] Expression Tree Build
    
                                                     
    Problem
The structure of Expression Tree is a binary tree to evaluate certain expressions.All leaves of the Expression Tree have an number string value. All non-leaves of the Expression Tree have an o...
    
                                                   
                          
    
                                
    
                                    qpal
                                    
                                    评论0 
                                    收藏0 
                                
    
                          
    
                      
    
                    
    •  
                                                                                       
  • 
                                                
    
                          
    表达式类算法题小结
    
                                                     
    摘要：将表达式转换为逆波兰式，然后求值转换中缀表达式为逆波兰式鲁棒性检测，表达式中没有操作数计算逆波兰式值参考

表达式类算法题小结
[TOC]
声明
文章均为本人技术笔记，转载请注明出处：[1] https://segmentfault.com/u/yzwall[2] blog.csdn.net/j_dark/
表达式分类
根据运算符与相关操作操作数的位置不同，将表达式分为前缀，中缀和后缀表...
    
                                                   
                          
    
                                
    
                                    Heier
                                    
                                    评论0 
                                    收藏0 
                                
    
                          
    
                      
    
                    
    •  
                                                                                       
  • 
                                                
    
                          
    [LintCode] Topological Sorting [BFS & DFS]
    
                                                     
    摘要：当队列非空时，拿出最后放入的元素。若减后入度为，则这个结点遍历完成，放入结果数组和队列。递归函数去遍历的，继续在中标记，使得所有点只遍历一次。最深的点最先，根结点最后，加入结果数组的头部处。

Problem
Given an directed graph, a topological order of the graph nodes is defined as follow:
For ...
    
                                                   
                          
    
                                
    
                                    draveness
                                    
                                    评论0 
                                    收藏0 
                                
    
                          
    
                      
    
                    
    •  
                                                                                       
  • 
                                                
    
                          
    js 中二叉树的深度遍历与广度遍历(递归实现与非递归实现)
    
                                                     
    摘要：树中结点的最大层次称为树的深度或高度。二叉树有深度遍历和广度遍历，深度遍历有前序中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等中序遍历可以实现表达式树，在编译器底层很有用后序遍历可以用来实现计算目录内的文件及其信息等。

树的简介
栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结...
    
                                                   
                          
    
                                
    
                                    Yuanf
                                    
                                    评论0 
                                    收藏0 
                                
    
                          
    
                      
    
                    
    •  
                                                                                       
  • 
                                                
    
                          
    [LintCode] Evaluate Reverse Polish Notation
    
                                                     
    摘要：中的运算符，运算之后要出来，继续遍历数组。是放入新的数字，用转换为均可。

Problem
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another ...
    
                                                   
                          
    
                                
    
                                    luckyyulin
                                    
                                    评论0 
                                    收藏0 
                                
    
                          
    
                      
    
                    
    •  
                                                                           
                

              

              
               

                  
                  
发表评论

                   

                                      
                      

                        登陆后可评论
                      
                   

               

              

                

                  
0条评论
   
                
 
                      

              

           
           

              
 
                

                    
                    
livem

                    
男|高级讲师

                    

                     
                                                                      
      
                                                                                        我要私信
                     
                                            
                    

                    

                          
TA的文章

                          阅读更多
                    

                      
                


                   
              
  

                  
最新活动
 
           
         

                    
                      
                    
                    
              


                    
                

                                
              

           

        
       
    
    
     

      
    

    
    

    
       
       

         
阅读需要支付1元查看