Question

Please help with this. The hint refers to the attached picture.

Read Section 6.1.5 (p.235) on the Parenthesis Matching problem. They gave 5 examples: the first two are " correct", and the remaining 3 "incorrect". Notice that the last one is actually "fixable". You just have to append the string")" to the input to get a properly matched expression! Here is another example: the string (O[(is incorrect, but is fixable if you append )]) Thus we want to classify the input expressions into " fixable" and" unfixable" When fixable, we want to return a string that can be appended to the input to be "correct". In particular, if a "correct" input is "fixable" (you just append the empty string). Write a method with this header: String isMatched(String expression); It should be similar to the code fragment 6.7 in page 236, except that we return a String. When the input expression is " unfixable", we return the string "X". If it is "fixable", return the string to fix the input string. HINT: you can reuse most of the code in page 236. 1/** Tests if delimiters in the given expression are properly matched./ 2 public static boolean isMatched(String expression) { 3 final String opening ' opening delimiters /respective closing delimiters 4 final String closing Stack-Character> buffer-new LinkedStack(); 6 for (char c : expression.toCharArray)) { if (opening. indexOf(c)--1) this is a left delimiter buffer.push(c); 9 else if (closing.indexOf(c) !--1){this is a right delimiter 10 if (buffer.isEmpty()) /nothing to match with return false; if (closing.indexOf(c) opening.indexOf (buffer.pop())) 12 13 14 15 16 return buffer.isEmpty); 17 return false; //mismatched delimiter // were all opening delimiters matched?

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

public static String isMatched(String expression) {

      final String opening = "({[";

      final String closing = ")}]";

      Stack<Character> buffer = new LinkedStack<Character>();

      for (char c : expression.toCharArray()) {

            if (opening.indexOf(c) != -1) {

                  buffer.push(c);

            } else if (closing.indexOf(c) != -1) {

                  if (buffer.isEmpty()) {

                        // unfixable

                        return "X";

                  }

                  if (closing.indexOf(c) != opening.indexOf(buffer.pop())) {

                        // unfixable

                        return "X";

                  }

            }

      }

      // fixable

      String appendable = "";

      // appending remaining closing characters corresponding to elemenets in

      // stack to a String variable that can be appended to expression to make

      // the expression fixable, if not.

      while (!buffer.isEmpty()) {

            // popping a char from buffer

            char c = buffer.pop();

            // finding index of c in opening

            int index = opening.indexOf(c);

            // appending corresponding closing bracket to string

            appendable += closing.charAt(index);

      }

      return appendable;

}