Statistics

Problem Statement for "ShortBooleanExp"

Problem Statement

You will be given a boolean expression in 2 variables a and b. The expression will resemble a normal arithmetic expression with the following exceptions:
  • 1) Multiplication denotes 'and'ing. For example, ab means a AND b.
  • 2) Addition denotes 'or'ing. For example, ab+b means (a AND b) OR b. As usual, multiplication has higher precedence than addition.
  • 3) If a variable is capitalized, it is negated. For example, Ab means (NOT a) AND b. As seen, negation has higher precedence than multiplication.
More formally, the input String exp will adhere to the following grammar: 
	<S> := <Term> | <S>+<Term>
	<Term> := a | b | A | B | <Term><Term>
Two boolean expressions have the same value if and only if they agree regardless of the truth values of a and b. You will return the shortest String that adheres to the grammar above, and is equivalent to exp in value. If two Strings have the same length, choose the lexicographically first one. The ordering of characters is +,A,B,a,b (same as in ASCII). As special cases, if the given expression is always true (regardless of the values of a and b) return "True" (quotes for clarity). Similarly, if the given expression is always false return "False".

Definition

Class:
ShortBooleanExp
Method:
getFirst
Parameters:
String
Returns:
String
Method signature:
String getFirst(String exp)
(be sure your method is public)

Constraints

  • exp will contain between 1 and 50 characters inclusive.
  • exp will adhere to the grammar given above.

Examples

  1. "AB+ab+abaB"

    Returns: "AB+ab"

  2. "b+AB+bB+B+aabbabab"

    Returns: "True"

  3. "bB+Aa+baAB"

    Returns: "False"

  4. "a+b+ab+ABa"

    Returns: "a+b"

  5. "ababababababababaaaaaaaaa+bbbbbbbbbbbbbbbb"

    Returns: "b"

  6. "AB+Ab+aB"

    Returns: "A+B"

  7. "AB"

    Returns: "AB"

  8. "Ab"

    Returns: "Ab"

  9. "A"

    Returns: "A"

  10. "Ba"

    Returns: "Ba"

  11. "B"

    Returns: "B"

  12. "Ab+Ba"

    Returns: "Ab+Ba"

  13. "A+B"

    Returns: "A+B"

  14. "ab"

    Returns: "ab"

  15. "AB+ab"

    Returns: "AB+ab"

  16. "b"

    Returns: "b"

  17. "A+b"

    Returns: "A+b"

  18. "a"

    Returns: "a"

  19. "B+a"

    Returns: "B+a"

  20. "a+b"

    Returns: "a+b"

  21. "ba+BAB+AbabababA+BabBaBAbA+BA+bababab+Ababab"

    Returns: "AB+ab"

  22. "AB"

    Returns: "AB"

  23. "Ab"

    Returns: "Ab"

  24. "A"

    Returns: "A"

  25. "Ba"

    Returns: "Ba"

  26. "B"

    Returns: "B"

  27. "Ab+Ba"

    Returns: "Ab+Ba"

  28. "A+B"

    Returns: "A+B"

  29. "ab"

    Returns: "ab"

  30. "AB+ab"

    Returns: "AB+ab"

  31. "b"

    Returns: "b"

  32. "A+b"

    Returns: "A+b"

  33. "a"

    Returns: "a"

  34. "B+a"

    Returns: "B+a"

  35. "a+b"

    Returns: "a+b"

  36. "abA+Ba+ba+a+BabababA+bA+BA+ab+aB+aB+aB+abab"

    Returns: "True"

  37. "ABbbA+BbABaBaBA+bBba+AbBBbbBBaAB+BAAaBabbbaabba+Aa"

    Returns: "False"

  38. "aaaaAaaBaBbaabAAb+ABABAA+baaBbbabA+bBBbaAA+bAaBbAb"

    Returns: "AB"

  39. "bAb+bBAAabBaabB+bBAa+bbabbABBAbA+bBabBBA+abaBb+bBb"

    Returns: "Ab"

  40. "A+AbaabaaaB+aaaaAAbbB+aA+bAAaBB+bbabbA+ABbBABB+bBb"

    Returns: "A"

  41. "aBBa+aaA+ABBbbBaAaBbBA+BbAB+abAB+bB+bAAAABabB+AaBb"

    Returns: "Ba"

  42. "AaB+bAbBab+aBabb+BBaaabB+Bb+bAabbA+AAABa+BB+AAbaAA"

    Returns: "B"

  43. "Abb+ABBAb+aA+baBaAaaBBBaaBaaBBABaa+Ab+bbAbA+BAb+aB"

    Returns: "Ab+Ba"

  44. "BaA+BAAa+BBbAB+aB+BA+Ba+aabB+A+abbBaaABBBA+AbBaAAB"

    Returns: "A+B"

  45. "ab+AAAa+aABaAbA+BbAabBAbAa+BaABBAbbAaBABAbaaBABaAb"

    Returns: "ab"

  46. "bbBAAaBbbbBAababaBAABB+bbaa+ABB+BaAb+bAaBBbaaABAAb"

    Returns: "AB+ab"

  47. "BbAAA+bBAaaA+ba+baab+aBA+baAb+bBAbaB+b+aBabBaB+Aaa"

    Returns: "b"

  48. "b+BAbBbbABaB+bbbBA+bbaBb+aABaA+baBa+baAa+A+babaBba"

    Returns: "A+b"

  49. "baB+ABa+BbBba+BaBbBaaAbaBBa+baaabAAABBabABAAAAAA+a"

    Returns: "a"

  50. "a+ABaaBAaBBb+aB+aBABAAaa+aABaabAABA+a+AaAB+B+BAb+a"

    Returns: "B+a"

  51. "aAbbaaBAAA+ABAAabbAaaABABBBbAaaa+bBBa+a+Ab+BbAbBaA"

    Returns: "a+b"

  52. "Ba+ba+AAb+Aa+B+aAbb+aaaabBbBAaaBBAB+AAa+aAaBbaBAAB"

    Returns: "True"

  53. "AB+Ab"

    Returns: "A"

  54. "aB+bA+ba"

    Returns: "a+b"

  55. "Ab+Ba"

    Returns: "Ab+Ba"

  56. "Ab+aB"

    Returns: "Ab+Ba"

  57. "aB"

    Returns: "Ba"

  58. "aBAB+aBaB+aBAb+aBab"

    Returns: "Ba"

  59. "a+B"

    Returns: "B+a"

  60. "A+aB"

    Returns: "A+B"

  61. "Ba"

    Returns: "Ba"

  62. "B+a"

    Returns: "B+a"

  63. "A+B"

    Returns: "A+B"

  64. "A+Ba"

    Returns: "A+B"

  65. "aB+BA+ab"

    Returns: "B+a"

  66. "aB+b"

    Returns: "a+b"

  67. "Ab+Aa"

    Returns: "Ab"

  68. "aB+Ba+ab"

    Returns: "a"

  69. "ab"

    Returns: "ab"

  70. "ababababababababaaaaaaaaa+bbbbbbbbbbbbbbbba"

    Returns: "ab"

  71. "Ab+a"

    Returns: "a+b"

  72. "BA+ba+Ba"

    Returns: "B+a"

  73. "aB+ab"

    Returns: "a"

  74. "ab+Ab+AB"

    Returns: "A+b"

  75. "Aaaaaaaaaaa+A+B"

    Returns: "A+B"

  76. "BA+ba"

    Returns: "AB+ab"

  77. "AB+Ab"

    Returns: "A"

  78. "A+b"

    Returns: "A+b"

  79. "AB+ab+Ab+Ba"

    Returns: "True"

  80. "Aaaaaaaaa+A+B"

    Returns: "A+B"

  81. "Aaaaaaaaa+Ab+Ba"

    Returns: "Ab+Ba"

  82. "ab+aB+Ab+AB"

    Returns: "True"

  83. "AB+ab+Ab"

    Returns: "A+b"

  84. "aB+bA"

    Returns: "Ab+Ba"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: