ShortBooleanExp
SRM 193 · 2004-05-05 · by brett1479
SRM 193 · 2004-05-05 · by brett1479 · Simple Math, String Parsing
Problem Statement
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:
String exp will adhere to the following grammar:
String that adheres to the grammar above, and is equivalent to exp in value. If two String s 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".
- 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.
<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
Constraints
- exp will contain between 1 and 50 characters inclusive.
- exp will adhere to the grammar given above.
Examples
0)
"AB+ab+abaB" Returns: "AB+ab"
1)
"b+AB+bB+B+aabbabab" Returns: "True"
2)
"bB+Aa+baAB" Returns: "False"
3)
"a+b+ab+ABa" Returns: "a+b"
4)
"ababababababababaaaaaaaaa+bbbbbbbbbbbbbbbb" Returns: "b"
Submissions are judged against all 84 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ShortBooleanExp with a public method string getFirst(string exp) · 84 test cases · 2 s / 256 MB per case