stack

• Stack

  • monotonic stack

  • parse expression

  • Calculator

  • Parentheses [TODO]

Stack

032.Longest-Valid-Parentheses (H) 155.Min-Stack (M) 225.Implement Stack using Queues (H-) 232.Implement-Queue-using-Stacks (H-) 341.Flatten-Nested-List-Iterator (M) 173.Binary-Search-Tree-Iterator (M) 536.Construct-Binary-Tree-from-String (M) 456.132-Pattern (H-) 636.Exclusive-Time-of-Functions (H-) 856.Score-of-Parentheses (M+) 946.Validate-Stack-Sequences（H-） 1190.Reverse-Substrings-Between-Each-Pair-of-Parentheses (H-) 1209.Remove-All-Adjacent-Duplicates-in-String-II (M+) 1586.Binary-Search-Tree-Iterator-II (H)

monotonic stack

042.Trapping-Rain-Water (H) 084.Largest-Rectangle-in-Histogram (H) 085.Maximal-Rectangle (H-) 255.Verify-Preorder-Sequence-in-Binary-Search-Tree (H) 402.Remove-K-Digits (H-) 316.Remove-Duplicate-Letters (H) 496.Next-Greater-Element-I (H-) 503.Next-Greater-Element-II (H-) 221.Maximal-Square (H-) 739.Daily-Temperatures (H-) 768.Max-Chunks-To-Make-Sorted-II (H-) 901.Online-Stock-Span (H-) 907.Sum-of-Subarray-Minimums (H) 1856.Maximum-Subarray-Min-Product (M+) 962.Maximum-Width-Ramp (H) 1019.Next-Greater-Node-In-Linked-List (M) 1063.Number-of-Valid-Subarrays (M+) 1124.Longest-Well-Performing-Interval (H) 1130.Minimum-Cost-Tree-From-Leaf-Values (H) 1673.Find-the-Most-Competitive-Subsequence (M) 1944.Number-of-Visible-People-in-a-Queue (H) 1950.Maximum-of-Minimum-Values-in-All=Subarrays (H-) 1966.Binary-Searchable-Numbers-in-an-Unsorted-Array (M+)

parse expression

071.Simplify-Path (M) 224.Basic-Calculator(H-) 227.Basic-Calculator-II (H-) 772.Basic-Calculator-III (H) 385.Mini-Parser (H) 439.Ternary-Expression-Parser (H-) 591.Tag-Validator (H) 726.Number-of-Atoms (M+) 1087.Brace-Expansion (H) 1096.Brace-Expansion-II (H) 1106.Parsing-A-Boolean-Expression (H-) 1896.Minimum-Cost-to-Change-the-Final-Value-of-Expression (H+)

Calculator

• Evaluate infix expression. The problem can have various follow-ups

  • How to define input: String s or String[] tokens. If input is defined as String s and numbers might include negative numbers, then parsing negative numbers can be kind of cumbersome. When possible, define input as String[] tokens. Even when required to define input as String s, double check whether we need to deal with negative numbers.

  • Whether contain space

  • Whether need to deal with parentheses

    def calculate(s: str) -> int:
      valStack = []
      opStack = []
      for i in range(s.length()):
        char token = s[i]
        if token == " ":
          continue
        elif token == "(":
          opStack.append(token)
        elif token == ")":
          while opStack[-1] != "(":
            valStack.append( calc( opStack.pop(), valStack.pop(), valStack.pop() ) )
          opStack.pop()
        elif token.isnumeric():
          start = i
          while i + 1 < s.len() and s[i+1].isnumeric():
            i++
          valStack.append(int(s[start:i + 1]))
        else:
          while !opStack.isEmpty() and isLowerPrece(token, opStack[-1]):
            valStack.append( calc( opStack.pop(), valStack.pop(), valStack.pop() ) )
          opStack.append( token )

      while opStack:
        valStack.append(calc( opStack.pop(), valStack.pop(), valStack.pop() ))

      return valStack.pop()
    }

    def isLowerPrece(curr: str, toBeCompared: str ) -> bool:
      return toBeCompared == '*' or toBeCompared == '/'
          or ( toBeCompared == '-' and ( curr == '+' or curr == '-' ) )

    def calc(operator: str, operand1: int, operand2: int) -> int:
      if operator == '+':
        return operand2 + operand1
      elif operator == '-':
        return operand2 - operand1
      elif operator == '*':
        return operand2 * operand1
      else
        return operand2 / operand1

Parentheses [TODO]

• Check if string s contains valid parenthese

  • Questions to confirm

    • Whether the string contains non-parentheses characters

    • Whether the string contains curly braces, brackets or parentheses

    • Need to calculate the invalid number or just judge it is valid or not

// Case 1: When only contains parentheses
// Judge whether a string is valid or not
boolean isValid( String s )
{
  int count = 0;
  for ( char ch : s.toCharArray() )
  {
    if ( ch == '(' )
    {
      count++;
    }
    else if ( ch == ')' )
    {
      if ( count == 0 )
      {
        return false;
      }
      count--;
    }
    // for non-parenthese chars, we will not process them
  }
  return count == 0;
}
int calcNumInvalid( String s )
{
  Stack<Character> stack = new Stack<>();
  for ( char ch : s.toCharArray() )
  {
    if ( ch == '(' ) 
    {
      stack.push( ch );
    }
    else if ( ch == ')' )
    {
      if ( !stack.isEmpty() && stack.peek() == '(' )
      {
        stack.pop();
      }
      else
      {
        stack.push( ch );
      }
    }
  }
  return stack.size();
}

// Case 2: If contains curly braces and brackets
// The basic idea is similar to Case 1. Things need to be changed here is using a Map<Ch, Ch> to store open and close mapping. 
boolean isValid( String s )
{
  Stack<Character> stack = new Stack<>();
  Map<Character, Character> openToClose = new HashMap<>();
  openToClose.put( '(', ')' );
  openToClose.put( '[', ']' );
  openToClose.put( '{', '}' );

  for ( char ch : s.toCharArray() )
  {
    if ( openToClose.containsKey( ch ) )
    {
      stack.push( ch );
    }
    else if ( openToClose.values.contains( ch ))
    {
      if ( stack.isEmpty() || ch != openToClose.get( stack.peek() ) )
      {
        return false;
      }
      stack.pop();
    }
  }

  return stack.size() == 0;
}