在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中使用可变栈的平衡括号算法

回答

相关问题