Removing unnecessary/duplicates parentheses from arithmetic expressions using stack(s)

Question

Write a program for finding duplicate parenthesis in a expression. For example :

(( a + b ) + (( c + d ))) = a + b + c + d
(( a + b ) * (( c + d ))) = (a + b) * (c + d)

One approach that I am aware of involves the following two steps:

Convert the given infix expression to postfix expression.
Convert back the postfix to infix

I don't want to do this entire process of converting from one representation to another, and then convert it back.

I want to do this using stack(s) but in a single pass. Is it possible ?

Please suggest an algorithm or share the code.

It's possible... depending on exactly how you define "a single pass". — keshlam, Nov 14 '14 at 04:40
By single pass, I mean traversing through the expression once. — OneMoreError, Nov 14 '14 at 15:20
What are the operations that you want to support? Only * - + / will do ? — Teddy, Nov 19 '14 at 12:20
The test expressions are too simple. I am not sure if it could be done in a single pass. For example, `((a+b/c) + ((d+e)) / (c) + (f+g)` results in an error because of missing closing parenthesis. I think you have to validate in one pass, and simplify on the next. But, I could be wrong. Do you also have to account for things like distributive property? — hfontanez, Nov 19 '14 at 16:04

FrankPl · Accepted Answer · 2014-11-21T07:20:01.413

You can use a recursive descent parser. This uses the function call stack implicitly, but not explicitly a Java stack. It can be implemented as follows:

public class Main {

    public static void main(String[] args) {
        System.out.println(new Parser("(( a + b ) + (( c + d )))").parse());
        System.out.println(new Parser("(( a + b ) * (( c + d )))").parse());
    }
}

public class Parser {
    private final static char EOF = ';';
    private String input;
    private int currPos;

    public Parser(String input) {
        this.input = input + EOF; // mark the end
        this.currPos = -1;
    }

    public String parse() throws IllegalArgumentException {
        nextToken();
        Result result = expression();
        if(currToken() != EOF) {
            throw new IllegalArgumentException("Found unexpected character '" + currToken() + "' at position " + currPos);
        }
        return result.getText();
    }

    // "expression()" handles "term" or "term + term" or "term - term"
    private Result expression() throws IllegalArgumentException {
        Result leftArg = term();

        char operator = currToken();
        if (operator != '+' && operator != '-') {
            return leftArg; // EXIT
        }
        nextToken();

        Result rightArg = term();

        if(operator == '-' && (rightArg.getOp() == '-' || rightArg.getOp() == '+')) {
            rightArg = encloseInParentheses(rightArg);
        }

        return new Result(leftArg.getText() + " " + operator + " " + rightArg.getText(), operator);
    }

    // "term()" handles "factor" or "factor * factor" or "factor / factor"
    private Result term() throws IllegalArgumentException {
        Result leftArg = factor();

        char operator = currToken();
        if (operator != '*' && operator != '/') {
            return leftArg; // EXIT
        }
        nextToken();

        Result rightArg = factor();

        if(leftArg.getOp() == '+' || leftArg.getOp() == '-') {
            leftArg = encloseInParentheses(leftArg);
        }
        if(rightArg.getOp() == '+' || rightArg.getOp() == '-' || (operator == '/' && (rightArg.getOp() == '/' || rightArg.getOp() == '*'))) {
            rightArg = encloseInParentheses(rightArg);
        }

        return new Result(leftArg.getText() + " " + operator + " " + rightArg.getText(), operator);
    }

    // "factor()" handles a "paren" or a "variable"
    private Result factor() throws IllegalArgumentException {
        Result result;
        if(currToken() == '(') {
            result = paren();
        } else if(Character.isLetter(currToken())) {
            result = variable();
        } else {
            throw new IllegalArgumentException("Expected variable or '(', found '" + currToken() + "' at position " + currPos);
        }
        return result;
    }

    // "paren()" handles an "expression" enclosed in parentheses
    // Called with currToken an opening parenthesis
    private Result paren() throws IllegalArgumentException {
        nextToken();
        Result result = expression();
        if(currToken() != ')') {
            throw new IllegalArgumentException("Expected ')', found '" + currToken() + "' at position " + currPos);
        }
        nextToken();
        return result;
    }

    // "variable()" handles a variable
    // Called with currToken a variable
    private Result variable() throws IllegalArgumentException {
        Result result = new Result(Character.toString(currToken()), ' ');
        nextToken();
        return result;
    }

    private char currToken() {
        return input.charAt(currPos);
    }

    private void nextToken() {
        if(currPos >= input.length() - 1) {
            throw new IllegalArgumentException("Unexpected end of input");
        }
        do {
            ++currPos;
        }
        while(currToken() != EOF && currToken() == ' ');
    }

    private static Result encloseInParentheses(Result result) {
        return new Result("(" + result.getText() + ")", result.getOp());
    }

    private static class Result {
        private final String text;
        private final char op;

        private Result(String text, char op) {
            this.text = text;
            this.op = op;
        }

        public String getText() {
            return text;
        }

        public char getOp() {
            return op;
        }
    }
}

If you want to use an explicit stack, you could convert the algorithm from a recursive one to an iterative one, using a stack of something similar to the Result inner class. In fact, the Java compiler/JVM converts each recursive algorithm to a stack based one putting the local variables onto a stack.

But recursive decent parsers are easily readable by humans, hence I would prefer the solution presented above.

Ross Taylor-Turner · Answer 2 · 2014-11-19T15:53:06.407

If you only care about duplicate parentheses (as the question seems to imply), rather than those deemed necessary due to operator precedence (as the other answers seem to imply) you can indeed use a stack to keep track of which brackets you have encountered, and decide that any non-whitespace non-bracket characters for each pair of parentheses matters, which gives you a much simpler iterative traversal using a stack:

public class BracketFinder {

    public List<BracketPair> findUnnecessaryBrackets(String input) {
        List<BracketPair> unneccessaryBrackets = new LinkedList<BracketPair>();
        Deque<BracketPair> bracketStack = new LinkedBlockingDeque<BracketPair>();

        for (int cursor = 0; cursor < input.length(); cursor++ ) {
            if (input.charAt(cursor) == '(') {
                BracketPair pair = new BracketPair(cursor);
                bracketStack.addLast(pair);
            } else if (input.charAt(cursor) == ')') {
                BracketPair lastBracketPair = bracketStack.removeLast();
                lastBracketPair.end = cursor;
                if (!lastBracketPair.isNecessary) {
                    unneccessaryBrackets.add(lastBracketPair);
                }
            } else if (input.charAt(cursor) != ' ') {
                if (!bracketStack.isEmpty()) {
                    bracketStack.getLast().isNecessary = true;
                }
            }
        }

        return unneccessaryBrackets;
    }

    class BracketPair {
        public int start = -1;
        public int end = -1;
        public boolean isNecessary = false;

        public BracketPair(int startIndex) {
            this.start = startIndex;
        }
    }
}

Which you can test with the following

    public static void main(String... args) {
        List<BracketPair> results = new BracketFinder().findUnnecessaryBrackets("(( a + b ) + (( c + d ))) = a + b + c + d");
        for (BracketPair result : results) {
            System.out.println("Unneccessary brackets at indices " + result.start + "," + result.end);
        }
    }

score 1 · Answer 3 · answered Nov 14 '14 at 13:08

Did not program it, but it could be look like this:

give the operations + / - the value 1 give the operations * & / the value 2 give the operation )( the value 2 (as its the same like *)

1 go to inner parenthesis and check if the next operation is higher in its value (means the parenthesis is necessary) or equal/lower to the own operation. if equal or lower the parenthesis is not necessary.

2 go to 1

you are finished, when there are no changes between 2 steps

hope this helped.. If you got an solution let me know please. If this didn't help, let me know too :)

Greetings

score 1 · Answer 4 · answered Nov 20 '14 at 17:01

Its possible in one pass. The idea is to look for previous / next operation around each () block and apply associativity rules. Here is small table with yes/no marks when () is necessary.

        // (a + b) + c NO
        // (a + b) - c NO
        // (a + b) / c YES
        // (a + b) * c YES

        // (a / b) + c NO
        // (a / b) - c NO
        // (a / b) / c NO
        // (a / b) * c NO

        // a + (b + c) NO
        // a - (b + c) YES
        // a / (b + c) YES
        // a * (b + c) YES

        // a + (b / c) NO
        // a - (b / c) NO
        // a / (b / c) YES
        // a * (b / c) NO


        // (a) ((a))   NO

Here is C++ code (im not sure if its not missing some cases - its just an idea):

string clear(string expression)
{
    std::stack<int> openers;
    std::stack<int> closers;
    std::stack<bool> isJustClosed;
    std::stack<char> prevOperations;
    std::stack<bool> isComposite;
    std::stack<int> toDelete;


    prevOperations.push(' ');
    isJustClosed.push(false);
    isComposite.push(false);

    string result = expression + "@";
    for (int i = 0; i < result.length(); i++)
    {
        char ch = result[i];

        if ((ch == '*') || (ch == '/') || (ch == '+') || (ch == '-') || (ch == '(') || (ch == ')') || (ch == '@'))
            if (isJustClosed.size() > 0)
                if (isJustClosed.top() == true) {

                    // pop all and decide!
                    int opener = openers.top(); openers.pop();
                    int closer = closers.top(); closers.pop();
                    char prev = prevOperations.top(); prevOperations.pop();
                    char prevOperationBefore = prevOperations.top();
                    isJustClosed.pop(); //isJustClosed.push(false);
                    bool isComp = isComposite.top(); isComposite.pop();

                    bool ok = true;
                    if (prev == ' ')
                        ok = false;
                    else
                    {
                        ok = false;
                        if (((isComp) || (prev == '+') || (prev == '-')) && (ch == '/')) ok = true;
                        if (((isComp) || (prev == '+') || (prev == '-')) && (ch == '*')) ok = true;

                        if (((isComp) || (prev == '+') || (prev == '-')) && (prevOperationBefore == '-')) ok = true;
                        if (prevOperationBefore == '/') ok = true;
                        if (((isComp) || (prev == '+') || (prev == '-')) && (prevOperationBefore == '*')) ok = true;
                    }


                    if (!ok)
                    {
                        toDelete.push(opener);
                        toDelete.push(closer);
                    }
                }

        if (ch == '(') {
            openers.push(i);
            prevOperations.push(' ');
            isJustClosed.push(false);
            isComposite.push(false);
        }

        if (ch == ')') {
            closers.push(i);
            isJustClosed.top() = true;
        }

        if ((ch == '*') || (ch == '/') || (ch == '+') || (ch == '-')) {
            if (!isComposite.top())
            {
                char prev = prevOperations.top();
                if ((ch == '+') || (ch == '-'))
                    if ((prev == '*') || (prev == '/'))
                        isComposite.top() = true;
                if ((ch == '*') || (ch == '/'))
                    if ((prev == '+') || (prev == '-'))
                        isComposite.top() = true;
            }
            prevOperations.top() = ch;
            isJustClosed.top() = false;
        }


    }

    while (toDelete.size() > 0)
    {
        int pos = toDelete.top();
        toDelete.pop();
        result[pos] = ' ';
    }
    result.erase(result.size() - 1, 1);

    return result;
}

Inside each block we track last operation and also track if content is composite like (a+b*c).

Test:

void test()
    {
        LOG << clear("((a + (a + b))) - ((c)*(c) + d) * (b + d)") << NL;
        LOG << clear("a + (a + b) - ((c) + d) * (b + d)") << NL;
        LOG << clear("(a/b)*(c/d)") << NL;
        LOG << clear("(a/b)*((((c)/d)))") << NL;
        LOG << clear("((a + b) - (c - d))") << NL;
        LOG << clear("((a + b)*((c - d)))+c/d*((a*b))") << NL;
        LOG << clear("a+a*b*(a/b)") << NL;
        LOG << clear("a+a*b*(a+b)") << NL;
    }

Result:

  a +  a + b    - ( c * c  + d) *  b + d 
 a +  a + b  - ( c  + d) *  b + d 
a/b * c/d 
a/b *    c /d   
 a + b  - (c - d) 
(a + b)*  c - d   +c/d*  a*b  
a+a*b* a/b 
a+a*b*(a+b)

score 0 · Answer 5 · edited May 23 '17 at 12:16

Personally I think there are at least 2 ways:

using a tree
using arithmetical polish notation

Tree

A tree can be created from the input expression. After the tree is created it can be flattened without the useless parentheses

Polish notation

(( a + b ) + (( c + d ))) will become (+ (+ a b) (+ c d))
(( a + b ) * (( c + d ))) will become (* (+ a b) (+ c d))

From here you could compare the each operand and the factors to see if they have the same priority in solving the arithmetical equation

I would go with the tree.

Removing unnecessary/duplicates parentheses from arithmetic expressions using stack(s)

5 Answers5