Удалите ненужные круглые скобки в Java ⇐ JAVA

[Anonymous]

Я пытаюсь удалить ненужные круглые скобки в выражении. На данный момент мой код обрабатывает большинство случаев использования, например:

Код: Выделить всё

Expression: 2 + (3 / -5) Result: 2 + (3 / -5)
Expression: x+(y+z)+(t+(v+w)) Result: x+y+z+t+v+w
Expression: 1*(2)+3   Result: 1*2+3
Expression: (1*2)*3   Result: 1*2*3
Expression: 1-(2+3)   Result: 1-(2+3)
Expression: 1(234)5   Result: 12345
Expression: 1*(2*3)*4 Result: 1*2*3*4
Expression: -(3*5)    Result: -3*5
Expression: -(3+5)    Result: -(3+5)
Expression: 1+(2+3)+4 Result: 1+2+3+4
Expression: -(3%5)    Result: -(3%5)
Expression: ((a+b)+(c+d)) Result: a+b+c+d
Expression: ((a+b))   Result: a+b
Expression: (a*b)     Result: a*b

Однако он не может обрабатывать такие выражения, как:

Код: Выделить всё

Expression: 1*(2+(3*(4+5))) Result: 1*2+3*4+5

Вывод должен быть: 1*2+3*(4+5), поскольку если мы удалим большинство внутренних круглых скобок, результат изменится, поэтому мы следует сохранить его.
Вот мой Java-код ниже, я чувствую, что может быть проблема с

Код: Выделить всё

areOperatorsCommutative

или containsOnlyCommutativeOperators.
Есть идеи, как это исправить, не нарушая других вариантов использования?

Как всякий раз, когда я обновляю свой код , я сломал что-то еще.

Код: Выделить всё

package com.test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class ExpressionOptimizer {

// Sets to store operators and high precedence operators
private static final Set operators = new HashSet(Arrays.asList('+', '-', '*', '/', '%'));
private static final Set highPrecedenceOperators = new HashSet(Arrays.asList('*', '/', '%'));
//   private static final Set lowPrecedenceOperators = new HashSet(Arrays.asList('+', '-'));
private static final Set lowPrecedenceOperators = new HashSet(Arrays.asList('+', '-'));

public static String removeUnnecessaryParentheses(String expression) {
// Handle null or empty input
if (expression == null || expression.isEmpty()) {
return expression; // Return the input as is if it's null or empty
}

StringBuilder sb = new StringBuilder();
int length = expression.length();
int[] open = new int[length]; // To track the depth of open parentheses
int[] close = new int[length]; // To track the depth of close parentheses

// Stack to keep track of open parenthesis indices
Stack stack = new Stack();
for (int i = 0; i < length; i++) {
char ch = expression.charAt(i);

if (ch == '(') {
stack.push(i);
open[i] = stack.size(); // Store the current depth of the open parenthesis
} else if (ch == ')') {
int openIndex = stack.pop();
close[openIndex] = stack.size() + 1; // Store the depth after popping
}
}

// New variables for deneme logic
int parenthesesLevel = 0;
boolean keepParentheses = false;

for (int i = 0; i < length; i++) {
char ch = expression.charAt(i);

if (ch == '(') {
parenthesesLevel++;
if (parenthesesLevel > 1 && containsAdditionOrSubtraction(expression, i)) {
keepParentheses = true;
sb.append(ch);
} else if (!isRedundant(expression, i, close)) {
sb.append(ch);
}
} else if (ch == ')') {
if (keepParentheses && parenthesesLevel >  1) {
sb.append(ch);
} else if (!isRedundant(expression, findMatchingOpenParenthesis(expression, i), close)) {
sb.append(ch);
}
parenthesesLevel--;
keepParentheses = false;
} else {
sb.append(ch);
}
}

return sb.toString();
}

/**
* Determines if the parentheses at the given index are redundant.
*
* @param expression the input expression
* @param openIndex  the index of the open parenthesis
* @param close      the array tracking the depth of close parentheses
* @return true if the parentheses are redundant, false otherwise
*/
private static boolean isRedundant(String expression, int openIndex, int[] close) {

int closeIndex = findMatchingCloseParenthesis(expression, openIndex);
String inside = expression.substring(openIndex + 1, closeIndex).trim();
char before = getPrecedingNonWhitespaceChar(expression, openIndex);
char after = getFollowingNonWhitespaceChar(expression, closeIndex);

if (inside.startsWith("-") && (before == '(' || operators.contains(before) || before == '#')) {
return false; // Retain parentheses for unary minus
}

if (containsAdditionSubtractionOrModulus(inside)) {
// Keep parentheses if preceded by a minus sign or followed by a high precedence operator
if (before == '-' || highPrecedenceOperators.contains(after) ) {
return false;
}
}

// Check for commutative operator conditions on both sides
boolean b1 = areOperatorsCommutative(before, after);
boolean b2 = containsOnlyCommutativeOperators(inside);
boolean b3 = containsOnlyNumbers(inside);
if ((b1 && b2) || b3) {
return true;
}

// Check for redundant parentheses due to operator precedence
return !containsHigherPrecedenceOperator(inside) && !affectsPrecedence(before, after);
}
private static char getPrecedingNonWhitespaceChar(String expression, int index) {
for (int i = index - 1; i >= 0; i--) {
if (!Character.isWhitespace(expression.charAt(i))) {
return expression.charAt(i);
}
}
return '#';
}
private static boolean containsAdditionSubtractionOrModulus(String expression) {
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if ( c == '+' || c == '%' || (c == '-' && i > 0 && !operators.contains(expression.charAt(i - 1)))) {
return true;
}
}
return false;
}

private static char getFollowingNonWhitespaceChar(String expression, int index) {
for (int i = index + 1; i < expression.length(); i++) {
if (!Character.isWhitespace(expression.charAt(i))) {
return expression.charAt(i);
}
}
return '#';
}
private static boolean containsOnlyNumbers(String inside) {
return inside.chars().allMatch(Character::isLetterOrDigit)  || inside.chars().allMatch(Character::isWhitespace);
}
private static boolean areOperatorsCommutative(char before, char after) {

return (before == '+' || before == '-' || before == '*' || before == '#' || before == '(') &&
(after == '+' || after == '-' || after == '*' || after == '#' || after == ')');
}

private static boolean containsHigherPrecedenceOperator(String inside) {
return inside.indexOf('*') != -1 || inside.indexOf('/') != -1 || inside.indexOf('%') != -1;
}

private static boolean affectsPrecedence(char before, char after) {
return (before == '/' || before == '%' || before == '*') || (after == '/' || after == '%' || after == '*');
}

private static boolean containsOnlyCommutativeOperators(String inside) {
// Check if the expression contains only +, -, *, parentheses, letters, digits, or whitespace
return inside.chars().allMatch(c ->  c == '+' || c == '-' || c == '*' || c == '(' || c == ')' ||
Character.isLetterOrDigit(c) || Character.isWhitespace(c));
}

private static int findMatchingCloseParenthesis(String expression, int openIndex) {
int depth = 1;
for (int i = openIndex + 1; i < expression.length(); i++) {
char ch = expression.charAt(i);
if (ch == ' ' || Character.isWhitespace(ch)) {
continue; // Skip whitespace characters
}
if (ch == '(') {
depth++;
} else if (ch == ')') {
depth--;
if (depth == 0) {
return i;
}
}
}
return -1; // Return -1 if no matching parenthesis is found
}

private static int findMatchingOpenParenthesis(String expression, int closeIndex) {
int depth = 1;
for (int i = closeIndex - 1; i >= 0; i--) {
if (expression.charAt(i) == ')') depth++;
else if (expression.charAt(i) == '(') {
depth--;
if (depth == 0) return i;
}
}
return -1; // Return -1 if no matching parenthesis is found
}
private static boolean containsAdditionOrSubtraction(String expression, int start) {
int initialLevel = 0;
int currentLevel = 0;

// Find the initial nesting level
for (int i = 0; i 

Подробнее здесь: [url]https://stackoverflow.com/questions/78747641/remove-unncessary-parentheses-in-java[/url]