Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Here is the implementation of the above algorithm. A few assumption:
1) String is properly formatted. I don't check whether there is a correct number of parenthesis etc
2) There is no spaces between the characters
3) Only following operators are allowed: '+', '-', '*','/'
Code:
public static void main(String[] args) {
System.out.println(removeParenthesis(new StringBuilder("((a*b)+c*(e+f))")));
System.out.println(removeParenthesis(new StringBuilder("(a+(b*c))*(d*(f*j))")));
System.out.println(removeParenthesis(new StringBuilder("(a+(b))")));
System.out.println(removeParenthesis(new StringBuilder("((a+b)+((c+d)))")));
}
public static String removeParenthesis(StringBuilder sb) {
if (removeParenthesis(null, sb, 0)) {
sb.deleteCharAt(0);
}
return sb.toString();
}
public static boolean removeParenthesis(Integer leftPrecedence, StringBuilder sb, int start) {
Integer lastPrecedence = null;
Integer minPrecedence = null;
while (start < sb.length()) {
if (sb.charAt(start) == '(') {
if (removeParenthesis(lastPrecedence, sb, start + 1)) {
sb.deleteCharAt(start);
} else {
int count = 0;
do {
if (sb.charAt(start) == '(') {
count++;
} else if (sb.charAt(start) == ')') {
count--;
}
start++;
} while (start < sb.length() && count != 0);
continue;
}
} else if (sb.charAt(start) == ')') {
if(minPrecedence == null) {
sb.deleteCharAt(start);
return true;
}
Integer rightPrecedence = start == sb.length() - 1 || sb.charAt(start + 1) == ')' ? null
: getPrecedence(sb.charAt(start + 1));
if ((leftPrecedence != null && minPrecedence < leftPrecedence)
|| (rightPrecedence != null && minPrecedence < rightPrecedence)) {
return false;
} else {
sb.deleteCharAt(start);
return true;
}
} else if (sb.charAt(start) < 'a' || sb.charAt(start) > 'z') {
lastPrecedence = getPrecedence(sb.charAt(start));
if (minPrecedence == null || minPrecedence > lastPrecedence) {
minPrecedence = lastPrecedence;
}
}
start++;
}
return false;
}
public static int getPrecedence(char operator) {
switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
throw new IllegalArgumentException(">>" + operator + "<<");
}
Hi,
Here is my implementation with Java.
I assumed that :
1. Given expression is valid, which means all open brackets are closed.
2. Given expression can not be null.
3. Given expression does not contain negatives. (-a + b) negative a is not possible.
Here is the main class :
public class RemoveUselessBracketsInExpression {
public String removeBrackets(String expression) {
String cleanExpression = removeSpaces(expression);
String result = remove(cleanExpression);
return result;
}
private String remove(String expression) {
Tree tree = createExpressionTree(expression);
walkOnTreeAndRemoveBrackets(tree.head);
return createExpressionFromNode(tree.head);
}
private Tree createExpressionTree(String expression) {
Tree tree = new Tree();
tree.head = trimBracketsAndCreateNode(expression);
return tree;
}
private void walkOnTreeAndRemoveBrackets(Node node) {
node.hasBrackets = false;
hasInnerExpressionWithDifferentOperator(node);
}
private String createExpressionFromNode(Node node) {
StringBuilder sb = new StringBuilder();
if (node.hasBrackets) {
sb.append("(");
}
if (node.operator != 0) {
sb.append(createExpressionFromNode(node.left));
sb.append(node.operator);
sb.append(createExpressionFromNode(node.right));
} else {
sb.append(node.expression);
}
if (node.hasBrackets) {
sb.append(")");
}
return sb.toString();
}
private void hasInnerExpressionWithDifferentOperator(Node node) {
if (node.operator != 0) {
if (node.operator == node.left.operator
|| getPrecedence(node.operator) <= getPrecedence(node.left.operator)) {
node.left.hasBrackets = false;
}
if (node.operator == node.right.operator
|| getPrecedence(node.operator) <= getPrecedence(node.right.operator)) {
node.right.hasBrackets = false;
}
hasInnerExpressionWithDifferentOperator(node.left);
hasInnerExpressionWithDifferentOperator(node.right);
}
}
private Node trimBracketsAndCreateNode(String expression) {
boolean hasBrackets = false;
boolean contuniue = true;
String trimmedExpression = expression;
while (contuniue) {
hasBrackets = checkHasBrackets(trimmedExpression);
if (hasBrackets) {
trimmedExpression = trimmedExpression.substring(1, trimmedExpression.length() - 1);
}
if (!checkHasBrackets(trimmedExpression)) {
contuniue = false;
}
}
return createNode(trimmedExpression, hasBrackets);
}
private Node createNode(String expression, boolean hasBrackets) {
System.out.println(expression);
int operatorIndex = getOperatorIndex(expression);
Node node = new Node();
node.expression = expression;
if (operatorIndex != -1) {
node.operator = expression.charAt(operatorIndex);
}
if (operatorIndex == -1) {
node.hasBrackets = false;
} else {
node.hasBrackets = hasBrackets;
}
if (operatorIndex != -1) {
node.left = trimBracketsAndCreateNode(expression.substring(0, operatorIndex));
node.right = trimBracketsAndCreateNode(expression.substring(operatorIndex + 1));
}
return node;
}
private boolean checkHasBrackets(String expression) {
int openBrackets = 0;
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c == '(') {
openBrackets++;
}
if (c == ')') {
openBrackets--;
}
if (openBrackets == 0 && i < expression.length() - 1) {
return false;
}
}
return expression.charAt(0) == '(' && expression.charAt(expression.length() - 1) == ')';
}
private int getOperatorIndex(String expression) {
int openBrackets = 0;
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c == '(') {
openBrackets++;
}
if (c == ')') {
openBrackets--;
}
if (openBrackets == 0) {
if (c == '-' || c == '+' || c == '*' || c == '/') {
return i;
}
}
}
return -1;
}
private String removeSpaces(String expression) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c != ' ') {
sb.append(c);
}
}
return sb.toString();
}
private int getPrecedence(char operator) {
switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return -1;
}
}
class Tree {
Node head;
}
class Node {
Node left;
Node right;
String expression;
boolean hasBrackets;
char operator;
}
}
I tested this implementation with these cases :
(testing more than one case in a test is not practical, but I preferred to keep simple for this page)
public class RemoveUselessBracketsInExpressionTest {
private RemoveUselessBracketsInExpression ru;
@Before
public void setup() {
ru = new RemoveUselessBracketsInExpression();
}
@Test
public void test01() {
assertEquals("a", ru.removeBrackets("a"));
assertEquals("a", ru.removeBrackets(" a "));
assertEquals("a+b", ru.removeBrackets(" (a + b) "));
assertEquals("a+b+c", ru.removeBrackets(" ( a + ( b + c ) ) "));
assertEquals("a+b+c+d", ru.removeBrackets(" ( ( a + b ) + ( c + d ) ) "));
assertEquals("(a+b)*(c+d)", ru.removeBrackets(" ( ( a + b ) * ( c + d ) ) "));
assertEquals("a*(b+c)", ru.removeBrackets(" ( a * ( b + c ) ) "));
assertEquals("a-b*(c+d)", ru.removeBrackets(" ( a - b * ( c + d ) ) "));
assertEquals("a-b*c+d", ru.removeBrackets("a - b * c + d"));
assertEquals("a-b*c*d", ru.removeBrackets("a - b * (c * d)"));
assertEquals("a-b*c*d/e", ru.removeBrackets("a - b * c * (d / e)"));
assertEquals("a-b*c*d/e", ru.removeBrackets("a - (b * c) * (d / e)"));
assertEquals("a-(b+c)*d/e", ru.removeBrackets("a - (b + c) * (d / e)"));
assertEquals("(a-b+c)*d/e", ru.removeBrackets("(a - b + c) * (d / e)"));
assertEquals("(a-b+c)*d/e", ru.removeBrackets("(a - (b) + c) * (d / e)"));
assertEquals("a+b-c+d/e", ru.removeBrackets("(a + (b - c) + (d / e))"));
assertEquals("a+b-c+d/e", ru.removeBrackets("(a + ((b - c)) + (d / e))"));
assertEquals("a+b-c*d/e", ru.removeBrackets("a + b - c * d / e"));
assertEquals("(a*b-c)/(d-e)", ru.removeBrackets("((a * b) - c) / (d - e)"));
assertEquals("(a-b+c)/d-e", ru.removeBrackets("((a - b) + (c)) / d - e"));
assertEquals("(a+b*c)*d*f*j", ru.removeBrackets("(a + (b*c)) * (d * ( f * j) ) "));
}
}
public static String removeBracket(char[]c){
int openIndex = -1;
int closeIndex = -1;
int otherOther = 0;
int hit =0;
for(int i=0;i<c.length;i++){
if(c[i] == '(' && openIndex == -1){ // get Open index
openIndex = i;
}else{
if(c[i] == '('){
System.out.println("ignore Open @ - "+i);
otherOther++;
hit++;
}
}
if(c[i] == ')' && otherOther == 0 && closeIndex == -1){
closeIndex = i;
}else{
if(c[i] == ')'){
System.out.println("ignore Close @ - "+i);
otherOther--;
hit++;
}
}
}
char array[] = new char[c.length-hit];
hit =0;
for(int i =0;i<c.length;i++){
if( (c[i] == '(' && openIndex != i) || (c[i] == ')' && closeIndex != i)){
continue;
}
else{
array[hit++]=c[i];
}
}
return new String(array);
}
C++ approach using stacks. Runs in O(n):
{
string erase(string word, stack<int> mul)
{
while(!mul.empty())
{
word[mul.top()] = ' ';
mul.pop();
}
return word;
}
void filter(string & word)
{
for(int i = 0; i < word.length(); i++)
if(word[i] == ' ')
{
word.erase(i, 1);
i--;
}
}
string analyze(string word)
{
stack<int> saver;
stack<int> mul;
stack<int> sum;
stack<char> signs;
for(int i = 0; i < word.length(); i++)
{
if(word[i] == '(')
saver.push(i);
else if(word[i] == '*' || word[i] == '/')
{
signs.push(word[i]);
if(mul.size() > 0)
{
mul.push(saver.top());
saver.pop();
}
}
else if(word[i] == ')')
{
if(signs.top() == '*' || signs.top() == '/')
mul.push(i);
else
sum.push(i);
signs.pop();
}
else if(word[i] == '+' || word[i] == '-')
{
signs.push(word[i]);
if(sum.size() > 0)
{
sum.push(saver.top());
saver.pop();
}
}
}
word = erase(word, mul);
filter(word);
return word;
}
}
When I look at this question I was like
hmm, parse the expression tree and reduce ?
But then I think it can't possibly be asked in an interview. This is the kind of question for a homework. Not easy and simple at all.
I have 10-line code (like that of NL) but this won't deal with the case of redundancy for + and -. for example: (a + b) + c = a + b +c
The first solution above seems too long. Does anybody have any solution that is more plausible solution for an interview.
Or parsing the tree and reduce is the only way?
void main()
{
//string input = "(a + (b*c)) * (d * ( f * j) )";
// use more complicated input
string input = "(a * (b+c)) * (d * ( f * j) ) + ((e-d*r)*s) + (e-d*r*(r-e))";
Dictionary<int, int> brackets = new Dictionary<int, int>();
int level = 0;
StringBuilder sb = new StringBuilder(input);
for (int i = 0; i < sb.Length; i++)
{
if (sb[i] == '(')
{
brackets[level++] = i;
}
else if (sb[i] == ')')
{
int openIndex = brackets[brackets.Count - 1];
string temp = sb.ToString();
string middleString = temp.Substring(openIndex, i - openIndex + 1);
if (KeepBracket(middleString))
{
sb.Replace('+', '=', openIndex, i - openIndex + 1);
sb.Replace('-', '_', openIndex, i - openIndex + 1);
}
else
{
sb[openIndex] = ' ';
sb[i] = ' ';
}
brackets.Remove(brackets.Count - 1);
level--;
}
}
string result = sb.ToString();
result = result.Replace('_', '-').Replace('=', '+');
Console.WriteLine("Org string :" + input);
Console.WriteLine("Modified string:" + result);
}
public bool KeepBracket(string str)
{
if (str.Contains('+') || str.Contains('-'))
return true;
return false;
}
C# - simple string manipulation
void main()
{
//string input = "(a + (b*c)) * (d * ( f * j) )";
// use more complicated input
string input = "(a * (b+c)) * (d * ( f * j) ) + ((e-d*r)*s) + (e-d*r*(r-e))";
Dictionary<int, int> brackets = new Dictionary<int, int>();
int level = 0;
StringBuilder sb = new StringBuilder(input);
for (int i = 0; i < sb.Length; i++)
{
if (sb[i] == '(')
{
brackets[level++] = i;
}
else if (sb[i] == ')')
{
int openIndex = brackets[brackets.Count - 1];
string temp = sb.ToString();
string middleString = temp.Substring(openIndex, i - openIndex + 1);
if (KeepBracket(middleString))
{
sb.Replace('+', '=', openIndex, i - openIndex + 1);
sb.Replace('-', '_', openIndex, i - openIndex + 1);
}
else
{
sb[openIndex] = ' ';
sb[i] = ' ';
}
brackets.Remove(brackets.Count - 1);
level--;
}
}
string result = sb.ToString();
result = result.Replace('_', '-').Replace('=', '+');
Console.WriteLine("Org string :" + input);
Console.WriteLine("Modified string:" + result);
}
public bool KeepBracket(string str)
{
if (str.Contains('+') || str.Contains('-'))
return true;
return false;
}
/**
*
* @author Brett Stahlman
*/
import java.util.*;
import java.util.regex.*;
enum TokenType { LP, RP, VAR, OP, EOF }
class Token {
TokenType type;
String value;
// Caveat: The negative lookbehind matching whitespace is needed to avoid extra (empty) fields prior to operators
// and such. Without it, it appears that the positive lookahead in `\\s*(?=[...])' will match twice at the same
// location: once with leading whitespace, once without. I believe this is a bug in the engine. Vim handles the
// equivalent regex without the extra field.
public static final Pattern reSep = Pattern.compile("(?<!\\s)\\s*(?=[-+*/()])|(?<=[-+*/()])\\s*+|\\s+");
static final Pattern reVar = Pattern.compile("[a-zA-Z_][a-zA-Z_[0-9]]*");
Token(String s) {
if (s == null) {
type = TokenType.EOF;
value = null;
return;
}
switch (s) {
case "(":
type = TokenType.LP;
break;
case ")":
type = TokenType.RP;
break;
case "+":
case "-":
case "*":
case "/":
type = TokenType.OP;
break;
default:
Matcher m = reVar.matcher(s);
if (!m.matches())
throw new RuntimeException("Invalid var: " + s);
// Create var token.
type = TokenType.VAR;
}
value = s;
}
public TokenType getType() { return type; }
public String getValue() { return value; }
}
class Lexer {
Deque<Token> fifo = null;
Lexer(String s) {
// Create a FIFO to hold the tokens.
fifo = new LinkedList<Token>();
tokenize(s);
}
// Fill the FIFO with Token's
public void tokenize(String s) {
String[] toks = Token.reSep.split(s);
for (String tok : toks) {
fifo.addLast(new Token(tok));
}
// Add an EOF. TODO: Is this really necessary?
fifo.addLast(new Token(null));
}
public Token getTok() {
return fifo.pollFirst();
}
public Token peekTok() {
return fifo.peekFirst();
}
}
interface IElement {
String toString();
int getPrec();
}
interface ITerm extends IElement {
void add(IElement el);
}
class Op implements IElement {
private char op;
Op(char op) {
this.op = op;
}
public String toString() {
return " " + op + " ";
}
public char getOp() { return op; }
public int getPrec() {
return op == '+' || op == '-' ? 0 : 1;
}
}
class Var implements IElement {
String name;
Var(String name) {
this.name = name;
}
public String toString() { return name; }
public int getPrec() { return 1; }
}
class Term implements ITerm {
private List<IElement> els = new ArrayList<IElement>();
private int prec = 1;
Term(IElement... els) {
for (IElement el : els)
add(el);
}
public String toString() {
String ret = "";
for (IElement el : els) {
String elStr = el.toString();
if (el instanceof Term)
ret += "(" + elStr + ")";
else
ret += elStr;
}
return ret;
}
public void add(IElement el) {
if (el instanceof Op && el.getPrec() == 0)
// Can only decrease.
prec = 0;
els.add(el);
}
// Sub-term shouldn't have been a subterm; splice into this.
public void splice(Term subTerm) {
for (IElement el : subTerm.els) {
add(el);
}
}
public int getPrec() { return prec; }
}
enum State { EXPECT_OP, EXPECT_TERM }
class Parser {
Lexer tokener;
Term term;
public static int getOpPrec(String op) {
return op.equals("*") || op.equals("/") ? 1 : 0;
}
Parser(Lexer tokener) {
this.tokener = tokener;
term = parse(0);
}
public String toString() {
return term.toString();
}
public Term parse(int level) {
Token tok = null, nextTok = null;
Term term = new Term();
State state = State.EXPECT_TERM;
int prevPrec = 0, nextPrec = 0;
tok = tokener.getTok();
term_loop: while (tok != null) {
switch (tok.getType()) {
case VAR:
if (state == State.EXPECT_TERM) {
term.add(new Var(tok.getValue()));
state = State.EXPECT_OP;
} else {
throw new RuntimeException("Unexpected variable: " + tok.getValue());
}
break;
case OP:
if (state == State.EXPECT_OP) {
term.add(new Op(tok.getValue().charAt(0)));
state = State.EXPECT_TERM;
prevPrec = getOpPrec(tok.getValue());
} else {
throw new RuntimeException("Unexpected operator: " + tok.getValue());
}
break;
case LP:
if (state == State.EXPECT_TERM) {
// Recurse to get sub-term.
Term subTerm = parse(level + 1);
// See whether sub-term needed to be a sub-term.
// TODO: Currently, existence of EOF precludes the following if being entered.
if ((nextTok = tokener.peekTok()) != null) {
if (nextTok.getType() == TokenType.OP)
nextPrec = getOpPrec(nextTok.getValue());
else if (nextTok.getType() == TokenType.RP || nextTok.getType() == TokenType.EOF)
nextPrec = 0;
else
throw new RuntimeException("Unexpected token: " + nextTok.getValue());
if (prevPrec <= subTerm.getPrec() && subTerm.getPrec() >= nextPrec)
// Redundant parens! Splice the sub-term with redundant parens into current term.
term.splice(subTerm);
else
// Add sub-term as a sub-term.
term.add(subTerm);
}
state = State.EXPECT_OP;
} else {
throw new RuntimeException("Unexpected `('");
}
break;
case RP:
if (state == State.EXPECT_OP && level > 0)
return term;
else
throw new RuntimeException("Unexpected `)'");
case EOF:
break term_loop;
}
// Advance...
tok = tokener.getTok();
}
// Ok to end here?
if (state == State.EXPECT_TERM || level > 0)
throw new RuntimeException("Unexpected End-of-input");
return term;
}
}
public class SimplifyParens {
/**
* @param args the command line arguments
*/
// Usage: java -jar SimplifyParens "(a + b * (c / d - e * (f + g)) - h * (i))"
// Usage: java SimplifyParens "(a * (b / c) - d * ((e * f) / g) * (h - i * (j - k) - l))"
// Output:
// Original expression: (a * (b / c) - d * ((e * f) / g) * (h - i * (j - k) - l))
// Simplified expression: a * b / c - d * e * f / g * (h - i * (j - k) - l)
public static void main(String[] args) {
String sexp = String.join("", args);
Lexer tokener = new Lexer(sexp);
Parser parser = new Parser(tokener);
System.out.println("Original expression: " + sexp);
System.out.println("Simplified expression: " + parser.toString());
}
}
// vim:ts=4:sw=4:et:tw=120
def remove_dbl_brkts(input_str):
# get rid of spaces
input_str = input_str.replace(" ","")
open_cnt = 0
for i in range(0,len(input_str)):
if input_str[i]=="(":
if open_cnt>0:
print "remove "+ str(i)
s = list(input_str)
s[i] = " "
input_str = "".join(s)
open_cnt+=1
elif input_str[i]==")":
open_cnt-=1
if open_cnt>0:
print "remove "+ str(i)
s = list(input_str)
s[i] = " "
input_str = "".join(s)
return input_str.replace(' ','')
print remove_dbl_brkts("(a+(b*c))*(d*(f*j))")
#include <iostream>
#include<cstdlib>
using namespace std;
#define MAX 20
template <class T>
struct stack{
int top;
T a[MAX];
};
template <class T>
void push(stack<T> *s, T str ){
if(s->top >= MAX )
return;
s->top++;
s->a[s->top] = str;
return;
}
template <class T>
T pop(stack<T> *s){
T t = s->a[s->top];
s->top--;
return t;
}
template <class T>
void init_stack(stack<T> *s){
s->top =-1;
return;
}
int is_operator(char c){
if(c=='+' || c=='-' || c=='/' || c=='*'){
return 1;
}else
return 0;
}
int hasPrecedence(char a, char b){
if((a == '*' || a =='/' ) && ( b=='+' || b=='-')){
return 1;
}else if((a == '+' || a =='-' ) && ( b=='*' || b=='/') )
return -1;
else
return 0;
}
void process(char *s1 ){
stack <char> op;
stack <char*> strings;
init_stack(&op);
init_stack(&strings);
cout<<"Input ::"<<endl;
puts(s1);
for(int i=0; s1[i]!= '\0' ; i++){
if( is_operator(s1[i])){
push(&op,s1[i]);
}else{
if(s1[i]==')'){
if( (is_operator(s1[i+1]) && hasPrecedence( s1[i+1] , op.a[op.top] ) ==1 ) || ( s1[i+1]==')' && hasPrecedence( op.a[op.top] , op.a[op.top-1] ) == -1 ) ){
//need to parenthesize previous part
char *o2 = pop(&strings);
char *o1 = pop(&strings);
char *opr = new char[2];
opr[0] = pop(&op);
opr[1]='\0';
pop(&strings);
char* open = new char[2];
char* close = new char[2];
open[0] = '(';
close[0] = ')';
open[1]=close[1]='\0';
char *res = strcat(open,o1);
res = strcat(res,opr);
res = strcat(res,o2);
res = strcat(res,close);
push(&strings,res);
}
else if( (is_operator(s1[i+1]) && hasPrecedence( s1[i+1] , op.a[op.top] ) !=1 ) || ( s1[i+1]== ')' && hasPrecedence( op.a[op.top] , op.a[op.top-1] ) != -1 ) ){
char *o2 = pop(&strings);
char *o1 = pop(&strings);
pop(&strings);
char *opr = new char[2];
opr[0] = pop(&op);
opr[1]='\0';
char *res = strcat(o1,opr);
res = strcat(res,o2);
push(&strings,res);
}else if( s1[i+1]=='\0'){
char *o2 = pop(&strings);
char *o1 = pop(&strings);
char *opr = new char[2];
opr[0] = pop(&op);
opr[1]='\0';
pop(&strings);
char *res = strcat(o1,opr);
res = strcat(res,o2);
push(&strings,res);
}
}else{
char *res=new char[2];
res[0]= s1[i];
res[1]='\0';
push(&strings,res);
}
}
}
char z;
while( op.top >= 0 ){
z =pop(&op);
char *o2 = pop(&strings);
char *o1 = pop(&strings);
char *opr = new char[2];
opr[0] = z;
opr[1]='\0';
char *res = strcat(o1,opr);
res = strcat(res,o2);
push(&strings,res);
}
char *result = pop(&strings);
cout<<"Final result is :: ";
puts(result);
}
int main(int argc, const char * argv[])
{
char b[]="(a+(b*c))*(d*(f*j))";
process(b);
return 0;
}
stackoverflowdotcom/questions/18400741/remove-redundant-parentheses-from-an-arithmetic-expression
- nishu May 08, 2014Hope this will help you.....