Stack

2 flashcards · Other · by Steven Bui

1. 20. Valid Parentheses Given a string s which contains parentheses (), curly braces {}, and brackets [], determine if all open characters are closed by closed characters in the same order. ex. Input: ([{}]) Output: true ---------------------------------------------------------------------------------- public boolean method (String s) { .... }

   Approach: Create a stack of characters. For each character in the string, create a switch block, where for each open character, you add onto the stack and break. For every closed character, try popping off the same character but open. If the stack is empty or the character is wrong, return false. At the end, return true if the stack is empty. Code: public boolean method (String s) { ....Stack<Character> stack = new Stack<>(); ....for (char c : s.toCharArray) { ........switch (c) { ............c…

2. 71. Simplify Unix Path You are given the absolute path for a Unix file system (ex. /home/downloads/file), but you need to simplify it: A single period (.) represents the current directory A double period (..) means go back a directory level Multiple periods (....) is the same as a name of a directory level Multiple consecutive slashes (////) are the same as 1 slash The returned path should start with one slash and not end with a slash (unless it is the root '/'). It should also not include (.)…

   Approach: First, create a stack of String objects (each object representing a directory level name). Split the path into a String array. For all of the strings in the array, skip if the string is a period (representing the current directory) or empty (representing a multi-slash). Then, if the string is (..), pop from the stack if it is not empty. Otherwise, add the string to the slash. Then, when you are out of the loop, create a new StringBuilder and append 2 things into the String Builder: a…