Remove brackets from an algebraic string containing + and – operators

Last Updated : 14 Dec, 2022

Simplify a given algebraic string of characters, ‘+’, ‘-‘ operators and parentheses. Output the simplified string without parentheses.

Examples:

Input : "(a-(b+c)+d)"
Output : "a-b-c+d"

Input : "a-(b-c-(d+e))-f"
Output : "a-b+c+d+e-f"

The idea is to check operators just before starting of bracket, i.e., before character ‘(‘. If operator is -, we need to toggle all operators inside the bracket. A stack is used which stores only two integers 0 and 1 to indicate whether to toggle or not.

We iterate for every character of input string. Initially push 0 to stack. Whenever the character is an operator (‘+’ or ‘-‘), check top of stack. If top of stack is 0, append the same operator in the resultant string. If top of stack is 1, append the other operator (if ‘+’ append ‘-‘) in the resultant string.

Implementation:

C++

// C++ program to simplify algebraic string
#include <bits/stdc++.h>
using namespace std;
 
// Function to simplify the string
char* simplify(string str)
{
    int len = str.length();
 
    // resultant string of max length equal
    // to length of input string
    char* res = new char(len);
    int index = 0, i = 0;
 
    // create empty stack
    stack<int> s;
    s.push(0);
 
    while (i < len) {
          // Don't do any operation
        if(str[i] == '(' && i == 0) {
            i++;
              continue;
        }
       
        if (str[i] == '+') {
 
            // If top is 1, flip the operator
            if (s.top() == 1)
                res[index++] = '-';
 
            // If top is 0, append the same operator
            if (s.top() == 0)
                res[index++] = '+';
 
        } else if (str[i] == '-') {
            if (s.top() == 1) {
                  if(res[index-1] == '+' || res[index-1] == '-') res[index-1] = '+'; // Overriding previous sign 
                else res[index++] = '+';
            }
            else if (s.top() == 0) {
                  if(res[index-1] == '+' || res[index-1] == '-') res[index-1] = '-'; // Overriding previous sign
                else res[index++] = '-'; 
            }
        } else if (str[i] == '(' && i > 0) {
            if (str[i - 1] == '-') {
 
                // x is opposite to the top of stack
                int x = (s.top() == 1) ? 0 : 1;
                s.push(x);
            }
 
            // push value equal to top of the stack
            else if (str[i - 1] == '+')
                s.push(s.top());
        }
 
        // If closing parentheses pop the stack once
        else if (str[i] == ')')
            s.pop();
 
        // copy the character to the result
        else
            res[index++] = str[i];
        i++;
    }
    return res;
}
 
// Driver program
int main()
{
    string s1 = "(a-(b+c)+d)";
    string s2 = "a-(b-c-(d+e))-f";
    cout << simplify(s1) << endl;
    cout << simplify(s2) << endl;
    return 0;
}

Java

// Java program to simplify algebraic string
import java.util.*;
class GfG { 
 
// Function to simplify the string 
static String simplify(String str) 
{ 
    int len = str.length(); 
 
    // resultant string of max length equal 
    // to length of input string 
    char res[] = new char[len]; 
    int index = 0, i = 0; 
 
    // create empty stack 
    Stack<Integer> s = new Stack<Integer> (); 
    s.push(0); 
 
    while (i < len) { 
          // Don't do any operation
        if(str.charAt(i) == '(' && i == 0) {
            i++;
              continue;
        }
       
        if (str.charAt(i) == '+') { 
 
            // If top is 1, flip the operator 
            if (s.peek() == 1) 
                res[index++] = '-'; 
 
            // If top is 0, append the same operator 
            if (s.peek() == 0) 
                res[index++] = '+'; 
 
        } else if (str.charAt(i) == '-') { 
            if (s.peek() == 1) 
                res[index++] = '+'; 
            else if (s.peek() == 0) 
                res[index++] = '-'; 
        } else if (str.charAt(i) == '(' && i > 0) { 
            if (str.charAt(i - 1) == '-') { 
 
                // x is opposite to the top of stack 
                int x = (s.peek() == 1) ? 0 : 1; 
                s.push(x); 
            } 
 
            // push value equal to top of the stack 
            else if (str.charAt(i - 1) == '+') 
                s.push(s.peek()); 
        } 
 
        // If closing parentheses pop the stack once 
        else if (str.charAt(i) == ')') 
            s.pop(); 
               
        else if(str.charAt(i) == '(' && i == 0)
              i = 0;
        // copy the character to the result 
          else
            res[index++] = str.charAt(i); 
        i++; 
    } 
    return new String(res); 
} 
 
// Driver program 
public static void main(String[] args) 
{ 
    String s1 = "(a-(b+c)+d)"; 
    String s2 = "a-(b-c-(d+e))-f"; 
    System.out.println(simplify(s1)); 
    System.out.println(simplify(s2));
}
} 

Python3

# Python3 program to simplify algebraic String
 
# Function to simplify the String
 
 
def simplify(Str):
    Len = len(Str)
 
    # resultant String of max Length
    # equal to Length of input String
    res = [None] * Len
    index = 0
    i = 0
 
    # create empty stack
    s = []
    s.append(0)
 
    while (i < Len):
          if (Str[i] == '(' and i == 0): 
                i += 1
                continue
 
        if (Str[i] == '+'):
 
            # If top is 1, flip the operator 
            if (s[-1] == 1): 
                res[index] = '-'
                index += 1
 
            # If top is 0, append the 
            # same operator 
            if (s[-1] == 0):
                res[index] = '+'
                index += 1
 
        else if (Str[i] == '-'):
            if (s[-1] == 1): 
                res[index] = '+'
                index += 1
            else if (s[-1] == 0): 
                res[index] = '-'
                index += 1
        else if (Str[i] == '(' and i > 0):
            if (Str[i - 1] == '-'):
 
                # x is opposite to the top of stack 
                x = 0 if (s[-1] == 1) else 1
                s.append(x)
 
            # append value equal to top of the stack 
            else if (Str[i - 1] == '+'): 
                s.append(s[-1])
 
        # If closing parentheses pop
        # the stack once 
        else if (Str[i] == ')'): 
            s.pop() 
 
        # copy the character to the result 
        else:
            res[index] = Str[i]
            index += 1
        i += 1
    return res
 
# Driver Code
if __name__ == '__main__':
 
    s1 = "(a-(b+c)+d)"
    s2 = "a-(b-c-(d+e))-f"
    r1 = simplify(s1)
    for i in r1:
        if i != None:
            print(i, end = " ")
        else:
            break
    print()
    r2 = simplify(s2)
    for i in r2:
        if i != None:
            print(i, end = " ")
        else:
            break
 
# This code is contributed by PranchalK

C#

// C# program to simplify algebraic string
using System;
using System.Collections.Generic;
 
class GfG 
{ 
 
// Function to simplify the string 
static String simplify(String str) 
{ 
    int len = str.Length; 
 
    // resultant string of max length equal 
    // to length of input string 
    char []res = new char[len]; 
    int index = 0, i = 0; 
 
    // create empty stack 
    Stack<int> s = new Stack<int> (); 
    s.Push(0); 
 
    while (i < len)
    {
          // Don't do any operation
        if(str[i] == '(' && i == 0)
        {
            i++;
              continue;
        }
       
        if (str[i] == '+')
        { 
 
            // If top is 1, flip the operator 
            if (s.Peek() == 1) 
                res[index++] = '-'; 
 
            // If top is 0, append the same operator 
            if (s.Peek() == 0) 
                res[index++] = '+'; 
 
        } 
        else if (str[i] == '-')
        { 
            if (s.Peek() == 1) 
                res[index++] = '+'; 
            else if (s.Peek() == 0) 
                res[index++] = '-'; 
        }
        else if (str[i] == '(' && i > 0) 
        { 
            if (str[i - 1] == '-') 
            { 
 
                // x is opposite to the top of stack 
                int x = (s.Peek() == 1) ? 0 : 1; 
                s.Push(x); 
            } 
 
            // push value equal to top of the stack 
            else if (str[i - 1] == '+') 
                s.Push(s.Peek()); 
        } 
 
        // If closing parentheses pop the stack once 
        else if (str[i]== ')') 
            s.Pop();
       
        // copy the character to the result 
        else
            res[index++] = str[i]; 
        i++; 
    } 
    return new String(res); 
} 
 
// Driver code
public static void Main(String[] args) 
{ 
    String s1 = "(a-(b+c)+d)"; 
    String s2 = "a-(b-c-(d+e))-f"; 
    Console.WriteLine(simplify(s1)); 
    Console.WriteLine(simplify(s2));
}
} 
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
// Javascript program to simplify algebraic string
 
// Function to simplify the string 
function simplify(str)
{
    let len = str.length; 
   
    // resultant string of max length equal 
    // to length of input string 
    let res = new Array(len); 
    let index = 0, i = 0; 
   
    // create empty stack 
    let s = [];
    s.push(0); 
   
    while (i < len) { 
        // Don't do any operation
        if(str[i] == '(' && i == 0) {
            i++;
              continue;
        }
             
        if (str[i] == '+') { 
   
            // If top is 1, flip the operator 
            if (s[s.length-1] == 1) 
                res[index++] = '-'; 
   
            // If top is 0, append the same operator 
            if (s[s.length-1] == 0) 
                res[index++] = '+'; 
   
        } else if (str[i] == '-') { 
            if (s[s.length-1] == 1) 
                res[index++] = '+'; 
            else if (s[s.length-1] == 0) 
                res[index++] = '-'; 
        } else if (str[i] == '(' && i > 0) { 
            if (str[i - 1] == '-') { 
   
                // x is opposite to the top of stack 
                let x = (s[s.length-1] == 1) ? 0 : 1; 
                s.push(x); 
            } 
   
            // push value equal to top of the stack 
            else if (str[i - 1] == '+') 
                s.push(s[s.length-1]); 
        } 
   
        // If closing parentheses pop the stack once 
        else if (str[i] == ')') 
            s.pop(); 
             
        // copy the character to the result 
        else
            res[index++] = str[i]; 
        i++; 
    } 
    return (res).join(""); 
}
 
// Driver program 
let s1 = "(a-(b+c)+d)"; 
let s2 = "a-(b-c-(d+e))-f"; 
document.write(simplify(s1)+"<br>"); 
document.write(simplify(s2)+"<br>");
 
 
// This code is contributed by rag2127
</script>

Output

a-b-c+d
a-b+c+d+e-f

Time Complexity: O(N), Where N is the length of the given string.
Auxiliary Space: O(N)

Suggest improvement

Stack Permutations (Check if an array is stack permutation of other)

Range Queries for Longest Correct Bracket Subsequence Set | 2

Share your thoughts in the comments

Stack implementation in different language

Some questions related to Stack implementation

Easy problems on Stack

Intermediate problems on Stack

Hard problems on Stack