Valid Parentheses Checker

Given a string S that may include various characters and three types of brackets: parentheses ( ), square brackets [ ], and curly braces { }, determine whether the brackets in the string are valid. The string is considered valid if:

• Every opening bracket has a corresponding closing bracket of the same type.
• Brackets are closed in the correct order.

You can assume that other characters do not affect the bracket matching. The matching rules can be formally expressed as: for every opening bracket x there exists a corresponding closing bracket y such that \( y \text{ corresponds to } x \) in the pairs \( ( \leftrightarrow ) \), \( [ \leftrightarrow ] \), and \( \{ \leftrightarrow \} \).

Output True if the string’s parentheses are valid, otherwise output False.

inputFormat

A single line string representing the expression that may contain letters, operators, and brackets.

outputFormat

Print True if the expression contains valid parentheses, otherwise print False.## sample

a + b - (c * d)

True