Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

stackoverflowdotcom/questions/18400741/remove-redundant-parentheses-from-an-arithmetic-expression

Hope this will help you.....

- nishu May 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 + "<<");
    }

- hulkthedestroyer May 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Convert to postfix expression and back to infix.

- Noobie May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Above solution is failing for input like a-(b-c)

- sxp June 02, 2021 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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) ) "));
	}
}

- Yasin Efe May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Sumit Kawatra May 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}

- NL May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I like redundancy.

- Anonymous May 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Anonymous June 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- Dung Nguyen July 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }

- Dung Nguyen July 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 *
 * @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

- Brett Pershing Stahlman July 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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))")

- Sangkeun Matt Lee July 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Debanjan Datta September 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dfsdfsdf

- a June 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

question?id=5978736570662912

- Anonymous May 08, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More