Problem

You are given an algebraic expression s containing lowercase variables, the operators + and -, and possibly nested parentheses ( ). Return an equivalent expression with all parentheses removed and the signs adjusted so that the meaning is preserved. The output should not start with a +.

Input / Output

• Input: a valid expression string.
• Output: the simplified expression string.

Examples

Example 1 Input: s = "a-(b+c)" Output: "a-b-c"

Example 2 Input: s = "a-(b-(c-d)+e)" Output: "a-b+c-d-e" Explanation: Inside the outer minus, b becomes -b, -(c-d) becomes +c-d, +e becomes -e.

Example 3 Input: s = "(a+b)-(c-d)" Output: "a+b-c+d"

Constraints

• 1 <= |s| <= 10^5
• The expression is well-formed; there is no multiplication or division (only sign propagation matters).

Approach — Stack of signs

Every character inside a bracket is affected by the sign immediately in front of that bracket, and the effect compounds with the enclosing brackets. Keep a stack whose top holds the effective sign (+1 or -1) for the current nesting level.

Walk through the string:

1. Start with the stack containing +1 and a variable cur = +1 meaning "the sign to apply to the next operand".
2. On a variable: compute sign = cur × stack.top. Output - if sign is negative, + if positive and the output is non-empty, then the variable. Reset cur = +1.
3. On +: cur = +1. On -: cur = -1.
4. On (: push cur × stack.top (the sign that applies to everything inside), then reset cur = +1.
5. On ): pop.

Each character is processed once, so the algorithm is linear.

Complexity

• O(n)