Remove Redundant Parentheses
National Olympiad — Regional round (2020 season)
Submission name: brackets.cpp
Problem summary
Remove all unnecessary pairs of parentheses from a valid arithmetic expression over independent operands &, binary +,−,*,/ and parentheses. Equivalence is algebraic for the same operand values in their original order.
Input
One expression without spaces, using ASCII minus.
Output
An equivalent expression with all unnecessary parentheses removed.
Constraints
3 ≤ length ≤ 200,000; the input is valid; parentheses may be nested deeply.
Worked example
An independently prepared example for this explanation.
Input
((&+&)*&)/&
Output
(&+&)*&/&
Solution analysis
- Parse the expression into a binary tree with a shunting-yard stack. Operators of equal precedence associate left-to-right. Existing parentheses guide parsing but do not themselves become tree nodes.
- Render each node using its operator and its children. A lower-precedence child needs parentheses. A higher-precedence child does not. At equal precedence, the left child needs none; the right child needs them only under subtraction or division. Under addition or multiplication, removing right-child parentheses preserves the algebraic value, including subtraction or division within that child.
- For ((&+&)*&)/&, the addition must stay grouped as the left factor of multiplication. The outer multiplication is already the left operand of division and needs no parentheses. Thus the output is (&+&)*&/&. Both parsing and rendering use explicit stacks to support 200,000 nested characters.
Why it works
The shunting-yard reductions construct exactly the original precedence and grouping. Rendering preserves every subtree’s value: lower-precedence grouping is necessary, higher-precedence grouping is automatic, and equal-precedence regrouping is valid precisely for a left child or under associative addition/multiplication with rational arithmetic. A right child under subtraction/division must retain its grouping. These local conditions are necessary for independent operands and sufficient at every tree edge, so the resulting expression is equivalent and no emitted pair can be removed.
Watch out. Do not retain parentheses merely to preserve the identical syntax tree: algebraic addition and multiplication allow more removal. Right operands of subtraction and division are special. Avoid recursive parsing or rendering on deeply nested input.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<vector>
// Algorithm: Parse the expression into a binary tree with a shunting-yard stack.
using namespace std;
struct Node{
char symbol;
int left,right;
};
int priority(char symbol){
return symbol=='+'||symbol=='-'?1:2;
}
int main(){
string text;
cin>>text;
vector<Node>nodes;
vector<int>operands;
vector<char>operators;
auto reduce=[&](){
int right=operands.back();
operands.pop_back();
int left=operands.back();
operands.pop_back();
char symbol=operators.back();
operators.pop_back();
nodes.push_back({symbol,left,right});
operands.push_back(static_cast<int>(nodes.size())-1);
};
for(char symbol:text){
if(symbol=='&'){
nodes.push_back({'&',-1,-1});
operands.push_back(static_cast<int>(nodes.size())-1);
}
else if(symbol=='('){
operators.push_back(symbol);
}
else if(symbol==')'){
while(operators.back()!='('){
reduce();
}
operators.pop_back();
}
else{
while(!operators.empty()&&operators.back()!='('&&
priority(operators.back())>=priority(symbol)){
reduce();
}
operators.push_back(symbol);
}
}
while(!operators.empty()){
reduce();
}
struct Action{
int node;
char output;
bool parentheses;
};
vector<Action>stack{{operands.back(),0,false}};
string answer;
while(!stack.empty()){
Action action=stack.back();
stack.pop_back();
if(action.output){
answer+=action.output;
continue;
}
Node node=nodes[action.node];
if(action.parentheses){
answer+='(';
stack.push_back({-1,')',false});
}
if(node.symbol=='&'){
answer+='&';
continue;
}
auto needs=[&](int child,bool right){
if(nodes[child].symbol=='&'){
return false;
}
int childPriority=priority(nodes[child].symbol);
int ownPriority=priority(node.symbol);
return childPriority<ownPriority||
(childPriority==ownPriority&&right&&(node.symbol=='-'||node.symbol=='/'));
};
stack.push_back({node.right,0,needs(node.right,true)});
stack.push_back({-1,node.symbol,false});
stack.push_back({node.left,0,needs(node.left,false)});
}
cout<<answer<<'\n';
}