Remove parentheses from a plus/minus expression by propagating signs
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an algebraic expression made of single-letter variables, the operators `+` and `-`, and parentheses. Simplify it by removing every pair of parentheses: write the variables in their original left-to-right order, each with the sign it actually carries once all parentheses are opened. Repeated variables are not combined; the task is only to remove the parentheses and resolve the signs.
### Function Signature
```python
def simplify_expression(expression: str) -> str:
```
### Rules
The expression follows this grammar and contains no spaces:
```text
expression := ["-"] term (("+" | "-") term)*
term := letter | "(" expression ")"
```
- A unary minus can therefore appear only at the very start of the whole expression or right after an opening parenthesis. There is no unary plus.
- A minus sign directly before a term, binary or unary, applies to that term; when the term is a parenthesized group, it applies to every variable inside the group. A variable's sign is `-` if an odd number of minus signs apply to it, directly or through enclosing groups, and `+` otherwise.
- Output the variables in the order they appear in the input, each with its sign. Write the first variable with a leading `-` if its sign is `-` and with no sign otherwise; write every later variable preceded by `+` or `-`. The output contains no spaces and no parentheses.
- Every occurrence of a letter is its own term: `"a-(a)"` becomes `"a-a"`, never `""` or `"0"`.
### Constraints
- `1 <= len(expression) <= 10^5`
- `expression` contains only lowercase letters `a` to `z` and the characters `+`, `-`, `(` and `)`.
- `expression` is valid under the grammar: parentheses are balanced, no group is empty, and every operator has an operand on its right.
- Parentheses may be nested to a depth close to `len(expression) / 2`.
### Examples
**Example 1**
```text
Input: expression = "a-(b+c)"
Output: "a-b-c"
```
The minus before the group applies to both `b` and `c`.
**Example 2**
```text
Input: expression = "a-(b-c-(d+e))-f"
Output: "a-b+c+d+e-f"
```
`b` has one minus applying to it, the one before the outer group. `c` has two (its own and the outer group's), and so do `d` and `e` (the inner group's and the outer group's), so all three are `+`. `f` has one.
**Example 3**
```text
Input: expression = "-(a-(-b+c))"
Output: "-a-b+c"
```
The leading unary minus applies to everything. `a` has only that one, so it is `-`. `b` has three: its own unary minus, the minus before `(-b+c)`, and the leading one. `c` has two.
Overview: Given an algebraic expression of single-letter variables joined by plus and minus signs, with nested parentheses and unary minus, rewrite it without parentheses. Each variable keeps its position and takes the sign it effectively carries. The problem tests parsing, sign propagation through nested groups, and handling very deep nesting.
Read the full Oracle Software Engineer interview experience this question came from
You are given an algebraic expression made of single-letter variables, the operators `+` and `-`, and parentheses. Simplify it by removing every pair of parentheses: write the variables in their original left-to-right order, each with the sign it actually carries once all parentheses are opened. Repeated variables are not combined; the task is only to remove the parentheses and resolve the signs.
Implement `simplify_expression(expression)`, which returns the simplified expression as a string.
### Rules
The expression contains no spaces and follows this grammar:
```text
expression := ["-"] term (("+" | "-") term)*
term := letter | "(" expression ")"
```
- A unary minus can therefore appear only at the very start of the whole expression or right after an opening parenthesis. There is no unary plus.
- A minus sign directly before a term, binary or unary, applies to that term; when the term is a parenthesized group, it applies to every variable inside the group. A variable's sign is `-` if an odd number of minus signs apply to it, directly or through enclosing groups, and `+` otherwise.
- Output the variables in the order they appear in the input, each with its sign. Write the first variable with a leading `-` if its sign is `-` and with no sign otherwise; write every later variable preceded by `+` or `-`. The output contains no spaces and no parentheses.
- Every occurrence of a letter is its own term: `"a-(a)"` becomes `"a-a"`, never `""` or `"0"`.
### Example 1
```text
Input: expression = "a-(b+c)"
Output: "a-b-c"
```
The minus before the group applies to both `b` and `c`.
### Example 2
```text
Input: expression = "-(a-(-b+c))"
Output: "-a-b+c"
```
The leading unary minus applies to the whole group. `a` has only that one minus, so it is `-`. `b` has three: its own unary minus, the minus before `(-b+c)`, and the leading one. `c` has two, so it is `+`.
### Constraints
- `1 <= len(expression) <= 10^5`
- `expression` contains only lowercase letters `a` to `z` and the characters `+`, `-`, `(` and `)`.
- `expression` is valid under the grammar: parentheses are balanced, no group is empty, and every operator has an operand on its right.
- Parentheses may be nested to a depth close to `len(expression) / 2`.
Constraints
- 1 <= len(expression) <= 10^5
- expression contains only lowercase letters 'a' to 'z' and the characters '+', '-', '(' and ')', with no spaces.
- expression is valid under the grammar expression := ['-'] term (('+' | '-') term)*, term := letter | '(' expression ')': parentheses are balanced, no group is empty, and every operator has an operand on its right; a unary minus appears only at the very start or right after '(' and there is no unary plus.
- Parentheses may be nested to a depth close to len(expression) / 2.
Examples
Input: ('a',)
Expected Output: 'a'
Explanation: Minimum valid input: a single positive variable is written with no sign.
Input: ('-a',)
Expected Output: '-a'
Explanation: A lone unary minus makes the only variable negative, so the output starts with '-'.
Hints
- For each variable, count the minus signs that apply to it: the one written directly before its own term (binary or unary) plus one for every enclosing group that has a minus directly before it. Only whether that count is odd or even matters.
- A minus in front of a group stops applying at that group's closing parenthesis; the terms after it are back in the enclosing context.
- Nesting can be close to len(expression) / 2 levels deep, and a leading unary minus belongs only to the first term of the expression.