Remove Redundant Parenthesis

Intuitionparentheses are needed exactly where printed precedence loses structure

The expression's value is determined by its binary tree: every operator combines a left subtree and a right subtree. Parentheses in the input tell you which combinations must happen first, while precedence tells you which combinations would happen first even without parentheses. The task is therefore easier in two stages: recover that tree, then choose the smallest parentheses set that still prints the same tree.

When an operator is printed inside another operator, compare their precedences. A lower-precedence child must be wrapped, because the parent would otherwise execute before part of that child. A higher-precedence child is safe. Equal precedence is safe on the left because left-to-right evaluation already groups it correctly, but the right side needs care: subtraction and division change meaning when their right operand is regrouped.

Approachparse first, render second

1. 1Store every operand and every reduced operation as a node, and keep node indices on a value stack so the expression tree can be built without recursive calls.
2. 2When an operand appears, create its leaf node and push its index because it is now the newest complete subexpression.
3. 3When an opening parenthesis appears, push it onto the operator stack as a barrier, because operators outside the pair must not combine values inside it prematurely.
4. 4When an operator appears, reduce operators of at least the incoming precedence until an opening parenthesis or a weaker operator is reached, because left-to-right evaluation requires equal-precedence operations to be completed first.
5. 5When a closing parenthesis appears, reduce until the matching opening parenthesis is on top, then discard that opening marker because the resulting value already represents the entire grouped subexpression.
6. 6Reduce every remaining operator after scanning the input, leaving the root node index as the complete expression tree; skipping this final drain would lose the last operations.
7. 7Render the tree with an explicit work stack, passing each node its parent operator and whether it is the right child, because those two facts are exactly what determine whether parentheses are required.
8. 8For each operator node, emit an opening and closing pair only when its child has lower precedence or is an equal-precedence right child under a non-associative parent; push the right task before the left task so the LIFO stack prints left, operator, right.

Complexitylinear even when the input is deeply nested

Annotated solutionC++ · iterative parsing and iterative rendering · safe for depth near 100000

#include <string>
#include <vector>
using namespace std;

class Solution {
    struct Node {
        char op;
        char value;
        int left;
        int right;

        Node(char v) : op(0), value(v), left(-1), right(-1) {}
        Node(char o, int l, int r) : op(o), value(0), left(l), right(r) {}
    };

    vector<Node> nodes;

    int precedence(char c) {
        return (c == '+' || c == '-') ? 1 : 2;
    }

    void reduceTop(vector<int>& values, vector<char>& operators) {
        char op = operators.back();
        operators.pop_back();

        int right = values.back();
        values.pop_back();
        int left = values.back();
        values.pop_back();

        nodes.push_back(Node(op, left, right));
        values.push_back(static_cast<int>(nodes.size()) - 1);
    }

    bool needsParentheses(char parent, char child, bool isRightChild) {
        if (parent == 0 || child == 0) return false;

        int parentPrecedence = precedence(parent);
        int childPrecedence = precedence(child);

        if (childPrecedence < parentPrecedence) return true;
        if (childPrecedence > parentPrecedence) return false;
        if (!isRightChild) return false;

        return parent != '+' && parent != '*';
    }

public:
    string removeBrackets(string Exp) {
        nodes.clear();
        vector<int> values;
        vector<char> operators;

        for (char c : Exp) {
            if (c >= 'A' && c <= 'Z') {
                nodes.push_back(Node(c));
                values.push_back(static_cast<int>(nodes.size()) - 1);
            } else if (c == '(') {
                operators.push_back(c);
            } else if (c == ')') {
                while (!operators.empty() && operators.back() != '(') {
                    reduceTop(values, operators);
                }
                operators.pop_back();
            } else {
                while (!operators.empty() && operators.back() != '(' &&
                       precedence(operators.back()) >= precedence(c)) {
                    reduceTop(values, operators);
                }
                operators.push_back(c);
            }
        }

        while (!operators.empty()) {
            reduceTop(values, operators);
        }

        struct Task {
            int kind;
            int nodeId;
            char ch;
            char parent;
            bool isRightChild;
        };

        string answer;
        answer.reserve(Exp.size());

        vector<Task> work;
        work.push_back({0, values.back(), 0, 0, false});

        while (!work.empty()) {
            Task task = work.back();
            work.pop_back();

            if (task.kind == 1) {
                answer.push_back(task.ch);
                continue;
            }

            Node& current = nodes[task.nodeId];
            if (current.op == 0) {
                answer.push_back(current.value);
                continue;
            }

            bool wrap = needsParentheses(
                task.parent, current.op, task.isRightChild
            );

            if (wrap) {
                work.push_back({1, 0, ')', 0, false});
            }
            work.push_back({0, current.right, 0, current.op, true});
            work.push_back({1, 0, current.op, 0, false});
            work.push_back({0, current.left, 0, current.op, false});
            if (wrap) {
                work.push_back({1, 0, '(', 0, false});
            }
        }

        return answer;
    }
};

The parser is a shunting-yard construction, but its values are node indices instead of numbers. Every reduction removes one operator and its two child indices, creates one parent node, and pushes that parent back as a complete value. This preserves the original grouping in a compact tree. The opening parenthesis is only a barrier during parsing; it never becomes a node and therefore can never appear in the result by accident.

The renderer receives the parent operator and the child's side as context. For a lower-precedence child, omitting parentheses lets the parent bind too early. For an equal-precedence right child, omission changes the grouping for subtraction or division. The two exceptions, addition and multiplication, are safe here because their equal-precedence right combinations can be flattened without changing the arithmetic expression's value.

Common mistakesthe grouping rules are asymmetric