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++
#include <bits/stdc++.h>
using namespace std;
char* simplify(string str)
{
int len = str.length();
char* res = new char(len);
int index = 0, i = 0;
stack<int> s;
s.push(0);
while (i < len) {
if(str[i] == '(' && i == 0) {
i++;
continue;
}
if (str[i] == '+') {
if (s.top() == 1)
res[index++] = '-';
if (s.top() == 0)
res[index++] = '+';
} else if (str[i] == '-') {
if (s.top() == 1) {
if(res[index-1] == '+' || res[index-1] == '-') res[index-1] = '+';
else res[index++] = '+';
}
else if (s.top() == 0) {
if(res[index-1] == '+' || res[index-1] == '-') res[index-1] = '-';
else res[index++] = '-';
}
} else if (str[i] == '(' && i > 0) {
if (str[i - 1] == '-') {
int x = (s.top() == 1) ? 0 : 1;
s.push(x);
}
else if (str[i - 1] == '+')
s.push(s.top());
}
else if (str[i] == ')')
s.pop();
else
res[index++] = str[i];
i++;
}
return res;
}
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
import java.util.*;
class GfG {
static String simplify(String str)
{
int len = str.length();
char res[] = new char[len];
int index = 0, i = 0;
Stack<Integer> s = new Stack<Integer> ();
s.push(0);
while (i < len) {
if(str.charAt(i) == '(' && i == 0) {
i++;
continue;
}
if (str.charAt(i) == '+') {
if (s.peek() == 1)
res[index++] = '-';
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) == '-') {
int x = (s.peek() == 1) ? 0 : 1;
s.push(x);
}
else if (str.charAt(i - 1) == '+')
s.push(s.peek());
}
else if (str.charAt(i) == ')')
s.pop();
else if(str.charAt(i) == '(' && i == 0)
i = 0;
else
res[index++] = str.charAt(i);
i++;
}
return new String(res);
}
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
def simplify(Str):
Len = len(Str)
res = [None] * Len
index = 0
i = 0
s = []
s.append(0)
while (i < Len):
if (Str[i] == '(' and i == 0):
i += 1
continue
if (Str[i] == '+'):
if (s[-1] == 1):
res[index] = '-'
index += 1
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 = 0 if (s[-1] == 1) else 1
s.append(x)
else if (Str[i - 1] == '+'):
s.append(s[-1])
else if (Str[i] == ')'):
s.pop()
else:
res[index] = Str[i]
index += 1
i += 1
return res
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
|
C#
using System;
using System.Collections.Generic;
class GfG
{
static String simplify(String str)
{
int len = str.Length;
char []res = new char[len];
int index = 0, i = 0;
Stack<int> s = new Stack<int> ();
s.Push(0);
while (i < len)
{
if(str[i] == '(' && i == 0)
{
i++;
continue;
}
if (str[i] == '+')
{
if (s.Peek() == 1)
res[index++] = '-';
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] == '-')
{
int x = (s.Peek() == 1) ? 0 : 1;
s.Push(x);
}
else if (str[i - 1] == '+')
s.Push(s.Peek());
}
else if (str[i]== ')')
s.Pop();
else
res[index++] = str[i];
i++;
}
return new String(res);
}
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));
}
}
|
Javascript
<script>
function simplify(str)
{
let len = str.length;
let res = new Array(len);
let index = 0, i = 0;
let s = [];
s.push(0);
while (i < len) {
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();
else
res[index++] = str[i];
i++;
}
return (res).join("");
}
let s1 = "(a-(b+c)+d)";
let s2 = "a-(b-c-(d+e))-f";
document.write(simplify(s1)+"<br>");
document.write(simplify(s2)+"<br>");
</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)
Please Login to comment...