Remove parentheses from a plus/minus expression

Write a function simplify(expr: str) -> str that removes every parenthesis from an expression and gives each term the sign it really has.

Input. A valid expression made of:

• operands: variable names (letters, digits and _, starting with a letter, such as a or x1) and non-negative integers
• the binary operators + and -
• unary minus at the start of the expression or right after (
• parentheses, nested to any depth
• spaces, which you should ignore

There is no multiplication or division.

Output. An equivalent expression with no parentheses and no spaces:

• Keep the terms in the order they appear in the input.
• Each term has the sign it gets once all enclosing groups are expanded.
• Drop a leading +, but keep a leading -.
• Do not combine like terms: x-(x) becomes x-x.
• If the expression has no operands, return "0".

Constraints. 1 <= len(expr) <= 10^5. Nesting depth can be close to len(expr), so avoid deep recursion. Aim for O(n) time.

Example 1

simplify("m-(n-(p+q))")  ->  "m-n+p+q"

p and q are inside two groups that each have a - in front. The two minus signs cancel.

Example 2

simplify("-(u - 4) + (-(v))")  ->  "-u+4-v"

Part 2 (follow-up). Write simplify_combined(expr), which also combines like terms and sums the integers into one constant at the end. For example, "k-(j-k)+5-2" becomes "2k-j+3".