Remove brackets from an algebraic string containing + and – operators

Read

Discuss(20+)

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)

If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

Last Updated : 14 Dec, 2022