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

Question

Write a program to find duplicate brackets in an expression. For example:

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

One approach that I know of includes the following two steps:

• Convert this infix expression to a postfix expression.
• Convert postfix to infix

I do not want to do the whole process of converting from one view to another, and then convert it back.

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

Please suggest an algorithm or split the code.

Answer 1

You can use a recursive descent parser . This uses function call stacks implicitly, but not explicitly, in the 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 can convert the algorithm from recursive to iterative, using a stack that looks something like the inner class Result . In fact, the Java / JVM compiler converts each recursive algorithm onto the stack, based on pushing local variables onto the stack.

But recursive decent parsers are easy to read by people, so I would prefer the solution presented above.

Answer 2

If you most need parentheses are duplicates (it seems the question seems to be) and not those that are considered necessary due to operator precedence (as other answers say), you can really use the stack to keep track of which brackets you come across, and decide that any non-white characters without binding for each pair of parentheses matter , which gives you a much simpler iterative traversal using the 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; } } } 

What you can check 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); } } 

Answer 3

Did not program it, but it may look like this:

give operations +/- value 1 give operation * and / value 2 give operation) (value 2 (as the same as *)

 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 done when there is no change between two steps

hope this helps .. If you have a solution, let me know please. If this does not help, let me know :)

Hi

Answer 4

This is possible in one go. The idea is to look for the previous / next operation around each () block and apply the rules of associativity. Here is a small table with yes / no labels when () is needed.

  // (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 the C ++ code (I'm not sure if it is missing in 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 the last operation, and also track whether the 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 + da + a + b - ( c + d) * b + da/b * c/da/b * c /da + b - (c - d) (a + b)* c - d +c/d* a*b a+a*b* a/b a+a*b*(a+b) 

Answer 5

Personally, I think there are at least 2 ways:

• using a tree
• using arithmetic notation

Wood

A tree can be created from an input expression. After creating a tree, it can be flattened without useless parentheses

• Binary_expression_tree
• parsing-an-arithmetic-expression-and-building-a-tree

Polish notation

• (( a + b ) + (( c + d ))) becomes (+ (+ ab) (+ cd))
• (( a + b ) * (( c + d ))) becomes (* (+ ab) (+ cd))

From here you can compare each operand and factors to make sure that they have the same priority when solving the arithmetic equation

I would go with a tree.