Tutorialspoint.dev

Remove brackets from an algebraic string containing + and – operators

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

Examples:

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

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.

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) {
        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)
                res[index++] = '+';
            else if (s.top() == 0)
                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)";
    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) { 
        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(); 
  
        // 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)"
    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] == '+'): 
  
            # 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
  
        elif (Str[i] == '-'):
            if (s[-1] == 1): 
                res[index] = '+'
                index += 1
            elif (s[-1] == 0): 
                res[index] = '-'
                index += 1
        elif (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 
            elif (Str[i - 1] == '+'): 
                s.append(s[-1])
  
        # If closing parentheses pop
        # the stack once 
        elif (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)"
    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)
    
        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)"
    String s2 = "a-(b-c-(d+e))-f"
    Console.WriteLine(simplify(s1)); 
    Console.WriteLine(simplify(s2));
}
  
// This code has been contributed by 29AjayKumar


Output:

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

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

tags:

Stack Stack

leave a comment

code

1 Comments

load comments

Subscribe to Our Newsletter