Background

A string is well formed with respect to parentheses if the parentheses are balanced. An example well formed string is

(a+b*(d+(e))-f)

A string that is not well formed is

(a+b*(d+(e-g))

One way to see that it is not well formed is to count up left parentheses (there are three of them) versus right parentheses (there are two of them). Since these counts are different, the input is not well formed.

Unfortunately, that rule is not enough: another example of a not well-formed string is

)b(

Here the counts are the same, but the string is not well formed. In class it will be shown how, with the use of a stack, it is easy to check if a string is well formed.

For checking whether or not a string is well formed, we can just ignore everything but parentheses. The previous input examples become, when we ignore everything except parentheses,

( ( ( ) ) )

( ( ( ) )

) (

(Removing everything except parentheses is a kind of "filter" step.)

Algorithm

Checking the well-formed property turns out to be simple with this algorithm. Write down 0 on a line below the input parentheses (we'll put in some spaces to make things easier to read). Then, going from left to right, increase the previous number below a left parenthesis and decrease the number below a right parenthesis. The values are a kind of "nesting depth" of the input symbols. Here is an example

( ( ( ) ) )

0 1 2 3 2 1 0

The decision that this is well-formed is that the final value on the right is 0, and nowhere was there a negative value. Here's another example

( ) ( ) ( ( ) )

0 1 0 1 0 1 2 1 0

What about an input that is not well formed?

) (

0 -1 0

Because there was a negative value in the numbers, this input fails the well-formed test.

( ( ( ) ( ) )

0 1 2 3 2 3 2 1

That is another way that input is not well formed: the final number was 1, not 0.

More Complicated

Two useful contributions of the previous homework are (1) a Stack class, and (2) code that splits up input on the basis of whitespace and symbols. For this homework, the symbols will be different kinds of parentheses.

Although it is simple to deal with plain parentheses, by counting left to right, the problem becomes harder when we allow multiple kinds of parentheses: ( ) [ ] { } -- these are just different kinds of parentheses. The question is how to generalize the simple solution for one kind to having multiple kinds. This will also be discussed in class. An interesting puzzle to think about is how to recognize that

( [ ) ]

is not a well-formed input. The algorithm here is to use a stack, going left to right through the input, either pushing an input symbol on the stack, or popping a symbol off the stack in each step. If the stack is empty at the end of the input, then the input is well formed.

All types of left parenthesis, (, [, and {, are pushed onto the stack when they are encountered, going left to right. All types of right parenthesis, when they are encountered, should attempt to pop the stack (if the stack is empty, then the input is not well formed). The kind of left parenthesis returned by pop() should be exactly the same kind of right parenthesis which triggered the pop() -- if this is not true, then the input is not well formed.

More Kinds of Parenthesis

This topic is discussed in this page (Links to an external site.)Links to an external site., and will be part of unit tests.

What to Download

We have to wait until we know all students have finished submitting work for the previous homework before the IntelliJ project can be revealed. The file oct18.zip has solutions to the 11 October homework, so that everyone has a working Stack class and a Tokenizer.

In the project, you will find two source kotlin files and one testing file. The two source files are oct11.kt and oct18.kt. Don't change oct11.kt (unless you need to add println statements for debugging, that's fine) - the oct11.kt file has a working Stack and Tokenizer.

The file oct18.kt has some things already done. There is an interface WFF and a class EasyWFF which implements WFF. Part of the code is already done for you, you only need to work on the recognizer method. You can see in the existing code how it creates S, the Stack, and T, the Tokenizer. Then it calls T.addSymbol to add the parentheses, so that the input can be split up in a convenient way. If you don't understand what this code does, feel free to add a main() method, print some things, and get some confidence first.

There are many tests cases to satisfy, starting with easy ones.

Please complete the following code in Kotlin, Only Recognize class need to be completed everything else is completed, All teste cases should pass.

class StackError(): Error() // subtype of Error, just for Stack // Stack Interface interface Stack { val debug: String // for debugging, print entire stack  val size: Int // the stack's current number of elements  val isEmpty: Boolean // true if the stack is empty  fun clear() // empty the stack entirely  // both peek() and pop() throw StackError when stack is empty  fun peek(): T // return value on top of Stack  fun pop(): T // return element on top, plus remove that element  fun push(item:T) // push new item on top of stack  fun hasElem(value:T): Boolean // return true if stack contains value  } interface Tokenizer { fun addSymbol(s:String) // add symbol pair to Parser  fun tokenize(input:String): List // break apart  // input into list of Strings separated by  // (1) whitespace, and (2) symbols added previously } /**** Stack Implementation ****/ class EasyStack(): Stack { val store = mutableListOf() // implements the stack, initially empty  override val debug: String get() = "$store"  override val size: Int get() = store.size  override val isEmpty: Boolean get() = store.isEmpty() override fun clear() = store.clear() override fun peek(): T { if (isEmpty) throw StackError() else return store.last() } override fun pop(): T { if (isEmpty) throw StackError() val r = store.last() store.removeAt(store.size-1) return r } override fun push(item:T) { store.add(item) } override fun hasElem(value:T) = store.contains(value) } /**** Implementation of Tokenizer ****/ class EasyTokenizer(): Tokenizer { val symbols = mutableListOf() override fun addSymbol(s:String) { if (s in symbols) return  // add the symbol to the current list  symbols.add(s) // then sort symbols with longest strings first  symbols.sortBy { it.length } // first shortest first,  symbols.reverse() // then flip backwards  } private fun subtokenize(input: String): List { // input needs to be a string with no whitespace  val R = mutableListOf() // used to store output  var cursor = 0 // start at leftmost character of input  var currentToken = "" // we use currentToken in the loop  while (cursor < input.length) { // check if string at cursor matches one of the symbols  var symbolfound = false  for (sym in symbols) { if (sym.length > input.substring(cursor).length) continue  if (sym != input.substring(cursor, cursor + sym.length)) continue  // sym found at start of current cursor position  if (currentToken.length > 0) { // pause to add current token  R.add(currentToken) currentToken = ""  } R.add(sym) // then add matching symbol  symbolfound = true  cursor += sym.length  } if (!symbolfound) { currentToken = currentToken + input[cursor] cursor += 1 } } if (currentToken.length > 0) R.add(currentToken) return R } override fun tokenize(input: String): List { val R = mutableListOf() // first break apart input with any whitespace  val nonwhites = input.trim().split(Regex("\\s+")) // next, for each thing in nonwhites, tokenize it by symbols  for (word in nonwhites) { R.addAll(subtokenize(word)) } return R } } 

// define methods that recognizer will have interface WFF { fun addParens(left:String, right:String) // called to add parentheses fun recognize(input:String): Boolean // true if input is Well Formed } // this class implements the recognizer class EasyWFF(): WFF { val parenTable = mutableListOf>() val S = EasyStack() as Stack val T = EasyTokenizer() as Tokenizer // the addParens method is called to add a pair (left,right) to table override fun addParens(left: String, right: String) { parenTable.add(left to right) T.addSymbol(left) T.addSymbol(right) } override fun recognize(input: String): Boolean { val splitup = T.tokenize(input) // write some code here that uses stack S and the list in splitup return false } }

Following Unit Tests Must Pass.

class Oct18Test { @Test fun test1() { // try cases with one kind of parenthesis, ( and )  val P: WFF = EasyWFF() P.addParens("(", ")") assertTrue(P.recognize("(a + b)")) } @Test fun test2() { val P: WFF = EasyWFF() P.addParens("(", ")") assertFalse(P.recognize("(")) } @Test fun test3() { val P: WFF = EasyWFF() P.addParens("(", ")") assertFalse(P.recognize(")")) } @Test fun test4() { val P: WFF = EasyWFF() P.addParens("(", ")") assertFalse(P.recognize(")(")) } @Test fun test5() { val P: WFF = EasyWFF() P.addParens("(", ")") assertFalse(P.recognize("(a * b))")) } @Test fun test6() { val P: WFF = EasyWFF() P.addParens("(", ")") assertFalse(P.recognize("(x+y")) } @Test fun test7() { val P: WFF = EasyWFF() P.addParens("(", ")") assertTrue(P.recognize("(a*(2+b)/c)")) } @Test fun test8() { val P: WFF = EasyWFF() // finally we test with two kinds of parenthesis  P.addParens("(", ")") P.addParens("[","]") assertTrue(P.recognize("2+(E[1]*E[2])")) } @Test fun test9() { val P: WFF = EasyWFF() // finally we test with two kinds of parenthesis  P.addParens("(", ")") P.addParens("[","]") assertFalse(P.recognize("([)]")) } @Test fun test10() { val P: WFF = EasyWFF() // finally we test with two kinds of parenthesis  P.addParens("(", ")") P.addParens("[", "]") P.addParens("{", "}") P.addParens("(.", ".)") assertFalse(P.recognize("t > ( j = 5 .)")) } @Test fun test11() { val P: WFF = EasyWFF() // finally we test with two kinds of parenthesis  P.addParens("(", ")") P.addParens("[", "]") P.addParens("{", "}") P.addParens("/*", "*/") val expr = "f = {j:B[9], r:(e/3)} /* f is a set */"  assertTrue(P.recognize(expr)) } }