Remove brackets from an algebraic string containing + and – operators

Problem Statement

You are given a string s of size n representing an arithmetic expression with parenthesis. The problem “Remove brackets from an algebraic string containing + and – operators” asks us to create a function that can simplify the given expression.

Example

s = "a-(b+c)"

a-b-c

 s = a-(b-c-(d+e))-f

a-b+c+d+e-f

Algorithm to Remove brackets from an algebraic string containing + and – operators

1. Initialize a string s of size n representing an arithmetic expression with parenthesis.
2. Create another string to store the result. Initialize an integer variable index as 0 and a stack data structure of integer type and push / insert 0 in it.
3. After that, traverse through the given string. Check if the character at the current index is equal to ‘+’. And check if the element at the top of the stack is 1, update the result string at index + 1 as ‘-‘ else if the element at the top of the stack is equal to 0, update the result string at index + 1 as ‘+’.
4. Else if the character at the current index in the given string is equal to ‘-‘, check if the element at the top of the stack is equal to 1, update the result string at index + 1 as ‘+’ else if the element at the top of the stack is equal to 0, update the result string at index + 1 as ‘-‘.
5. Similarly, check if the character at the current index in the given string is equal to ‘(‘ and the current index is greater than 0, check if the character at the current index – 1 in the given string is equal to ‘-‘, create an integer variable and update it as 0 if the element at the top of the stack is equal to 1 else 0. Else if the character at the current index – 1 in given string is equal to ‘+’,  push the element at the top of the stack in stack itself.
6. After that, check if the character at the current index in the given string is equal to ‘)’, pop the element at the top of the stack.
7. Else update the result string at index + 1 as the character at the current index in the given string.

Code

C++ Program to Remove brackets from an algebraic string containing + and – operators

#include <bits/stdc++.h> 
using namespace std; 
  
char* simplify(string s){ 
    int n = s.length(); 
  
    char* res = new char(n); 
    int index = 0, i = 0; 
  
    stack<int> st; 
    st.push(0); 
  
    while(i < n){ 
        if(s[i] == '+'){ 
            
            if(st.top() == 1){ 
                res[index++] = '-';
            }
            
            if(st.top() == 0){ 
                res[index++] = '+'; 
            }
        } 
        
        else if(s[i] == '-'){ 
            
            if(st.top() == 1){ 
                res[index++] = '+';
            }
            
            else if(st.top() == 0){ 
                res[index++] = '-';
            }
        } 
        
        else if(s[i] == '(' && i > 0){ 
            
            if(s[i - 1] == '-'){ 
                int x = (st.top() == 1) ? 0 : 1; 
                st.push(x); 
            } 
  
            else if(s[i - 1] == '+'){ 
                st.push(st.top()); 
            }
        } 
  
        else if(s[i] == ')'){ 
            st.pop(); 
        }
  
        else{
            res[index++] = s[i];
        }
        i++; 
    } 
    return res; 
} 
  
int main(){ 
    string s = "a-(b+c)"; 
    cout << simplify(s) << endl; 
    return 0; 
}

a-b-c

Java Program to Remove brackets from an algebraic string containing + and – operators

import java.util.*; 

class SimplifyExp{  
  
    static String simplify(String s){  
        int n = s.length();  
      
        char res[] = new char[n];  
        int index = 0, i = 0;  
      
        Stack<Integer> st = new Stack<Integer> ();  
        st.push(0);  
      
        while(i < n){  
            if(s.charAt(i) == '+'){  
      
                if(st.peek() == 1){  
                    res[index++] = '-';
                }
      
                if(st.peek() == 0){  
                    res[index++] = '+';
                }
            } 
            
            else if(s.charAt(i) == '-'){  
                
                if(st.peek() == 1){  
                    res[index++] = '+';
                }
                
                else if(st.peek() == 0){  
                    res[index++] = '-'; 
                }
            } 
            
            else if(s.charAt(i) == '(' && i > 0){
                
                if(s.charAt(i - 1) == '-'){  
                    int x = (st.peek() == 1) ? 0 : 1;  
                    st.push(x);  
                }  
      
                else if(s.charAt(i - 1) == '+'){  
                    st.push(st.peek());  
                }
            }  
      
            else if(s.charAt(i) == ')'){  
                st.pop();  
            }
      
            else{
                res[index++] = s.charAt(i);
            }
            i++;  
        }  
        return new String(res);  
    }  
      
    public static void main(String[] args){  
        String s = "a-(b+c)";  
        System.out.println(simplify(s));  
    } 
}

a-b-c

Complexity Analysis

Time Complexity

O(n) where n is the number of the characters in the given string. As we can see that we are traversing over the elements of the given input string. Thus the time complexity is linear.

Space Complexity

O(n) because we used space to store characters. Since we have created a new string to store the output the space complexity is also linear.