Remove brackets from an algebraic expression

In this article, we will solve the most asked interview question: “Remove brackets from an algebraic expression”

Problem Statement: 

Remove brackets from an algebraic expression

Write a program to remove brackets from an algebraic expression

Given an algebraic expression, we need to simplify the expression and remove the brackets.

Examples:

Example 1:
Input: “a+((b-c)+d)”
Output: “a+b-c+d”
Explanation: Removed all the brackets in the algebric expression.

Example 2:
Input: “(((a-b))+c)”
Output: “a-b+c”
Explanation: Removed all the brackets in the algebric expression.

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution:

Intuition:

An input string will contain characters. If the character is “(“ or “)”, we know that we have to ignore it in the answer.

We iterate over the input string and check each character, if it is not a bracket, we will append it to the answer string.

Approach:

  • Take an answer string.
  • Set a loop to parse the input string.
  • If the character is not “(“ ,“)”; we simply add it to our answer string.
  • If the character is “(“ or “)”, we can ignore it.
  • At last return the answer string as our answer.

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;


string solve(string input){
    string answer;
    for(int i=0;i<input.size();i++){
        if(input[i] != '(' && input[i] != ')')
            answer.push_back(input[i]);
    }
    return answer;
}


int main() {

  string input1 = "a+((b-c)+d)";
  string input2 = "(((a-b))+c)";
  
  
  cout<<"Original String: "<<input1<<endl;
  cout<<"After removing brackets: "<<solve(input1)<<endl;
  cout<<"Original String: "<<input2<<endl;
  cout<<"After removing brackets: "<<solve(input2)<<endl;
}

Output:

Original String: a+((b-c)+d)
After removing brackets: a+b-c+d
Original String: (((a-b))+c)
After removing brackets: a-b+c

Time Complexity: O(N)

Reason: We iterate from 0 to n-1.

Space Complexity: O(1)

Reason: We are  not using any extra space.

Java Code

import java.io.*;
import java.util.*;

class takeuforward {


  static String solve(String input) {
   
     StringBuilder answer = new StringBuilder("");
     for(int i=0 ; i<input.length(); i++){
         if(input.charAt(i)!='(' && input.charAt(i) != ')' )
            answer.append(input.charAt(i));
     }
     return answer.toString();
  }

  public static void main(String[] args) {

    String input1 = "a+((b-c)+d)";
    String input2 = "(((a-b))+c)";

    System.out.println("Original String: "+input1);
    System.out.println("After removing brackets: "+solve(input1));
    System.out.println("Original String: "+input2);
    System.out.println("After removing brackets: "+solve(input2));
    
  }
}

Output:

Original String: a+((b-c)+d)
After removing brackets: a+b-c+d
Original String: (((a-b))+c)
After removing brackets: a-b+c

Time Complexity: O(N)

Reason: We iterate from 0 to n-1.

Space Complexity: O(1)

Reason: We are not using any extra space. 

Special thanks to Anshuman Sharma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article