Simplifica una string algebraica dada de caracteres, operadores ‘+’, ‘-‘ y paréntesis. Muestra la string simplificada sin paréntesis.
Ejemplos:
Input : "(a-(b+c)+d)" Output : "a-b-c+d" Input : "a-(b-c-(d+e))-f" Output : "a-b+c+d+e-f"
La idea es verificar los operadores justo antes de comenzar el corchete, es decir, antes del carácter ‘(‘. Si el operador es -, necesitamos cambiar todos los operadores dentro del corchete. Se usa una pila que almacena solo dos números enteros 0 y 1 para indicar si alternar o no.
Iteramos para cada carácter de la string de entrada. Inicialmente presione 0 para apilar. Siempre que el carácter sea un operador (‘+’ o ‘-‘), marque la parte superior de la pila. Si la parte superior de la pila es 0, agregue el mismo operador en la string resultante. Si la parte superior de la pila es 1, agregue el otro operador (si ‘+’ agregue ‘-‘) en la string resultante.
Implementación:
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>
Producción
a-b-c+d a-b+c+d+e-f
Este artículo es una contribución de Chhavi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA