在scala中使用可變棧的平衡括號算法

我最近接受了scala的訪問。問題是要解決給定的字符串是否有平衡括號。例如，「（（{（{}]）」是平衡的，其中「（（（{）}））」不是。在scala中使用可變棧的平衡括號算法

我在下面提供的解決方案 -

object BalancedBrackets { 

     def main(a: Array[String]): Unit = { 
     println(balancedBrackets("((()))")) 
     } 


     def balancedBrackets(s: String): Boolean = { 

     import scala.collection.mutable.Stack 
     import scala.util.control.Breaks._ 
     var brackets = Stack[Char]() 
     try { 
      for (c <- s) { 
      println(c) 
      c match { 
       case '(' | '{' | '[' => brackets.push(c) 
       case ')' => var c1 = brackets.pop; if (c1 != '(') { 
       break 
       } 
       case '}' => var c1 = brackets.pop; if (c1 != '{') { 
       break 
       } 
       case ']' => var c1 = brackets.pop; if (c1 != '[') { 
       break 
       } 
      } 
      } 

      if (brackets.size == 0) true else false 
     } catch { 
      case ex: Exception => println("Exception"); ex.printStackTrace(); false 
     } 
     } 

    }

但記者問到用一成不變的堆棧，而不是作爲可變可變不是線程安全的，如預期在多線程環境將無法正常工作。

我不知道如何在scala中使用不可變堆棧實現相同的算法。任何人都可以幫助我。

來源

2016-07-24 Rajkumar Natarajan

參見此：http://stackoverflow.com/a/10941738/5599298 – slouc

下面是解：http://stackoverflow.com/a/12556621/4496364 –

的[算法可能的複製轉換爲Scala的，看不出爲什麼它不起作用]（http://stackoverflow.com/questions/12555162/algorithm-converted-to-scala-cant-see-why-it-doesnt-work） –

我readed您的問題和I`ve想出了這個解決方案：

def balancedBrackets(s: String): Boolean = 
      s.substring(0,s.length/2) == s.substring(Math.floorDiv(s.length(),2)).map { 
      x => if(x == ')') '(' 
       else if(x == ']') '[' 
       else if(x == '}') '{' 
       }.mkString.reverse

正如你可以看到有沒有狀態突變。

如果你想與Scala一起工作，你必須在功能性編程上多一點搜索。

我建議您閱讀「Scala中的函數式編程」和「Scala中的編程」都是很棒的書！我將從「Scala函數式編程」開始，因爲它會向您介紹這種新的編程範例。

來源

2016-07-25 00:07:57

由於您的解決方案堆棧僅包含括號。如果文本中的下一個括號與堆棧中的頂部括號相匹配，則會被刪除，否則堆棧會增長當結果堆棧爲空時，方括號被認爲是平衡的。

foldLeft的主要優點是它的摘要超過for循環。從循環剩下的是從先前結果和當前值到下一個結果(Stack[Char], Char) => Stack[Char]的函數。這種簽名鼓勵爲每次迭代返回新的堆棧。

def balanced(text: String): Boolean = { 
    val parenthesis = Map('}' -> '{', ')' -> '(', ']' -> '[', '>' -> '<') 

    val isParenthesis: (Char) => Boolean = c => parenthesis exists { case (closed, opened) => closed == c || opened == c } 
    val isClosing: (Char) => Boolean = parenthesis.contains 
    val openingFor: (Char) => Option[Char] = parenthesis.get 

    text.toCharArray 
    .filter(isParenthesis) 
    .foldLeft(Stack[Char]())((stack, p) => { 
     if (isClosing(p) && openingFor(p) == stack.headOption) stack.pop 
     else stack.push(p) 
    }).isEmpty 
}

來源

2016-07-25 13:26:24

在scala中使用可變棧的平衡括號算法

回答

相關問題