Amazon Interview Question Developer Program Engineers
Country: India
Interview Type: In-Person
Hi!
I would use two stacks :
- numbers (will contain only numbers)
- operators (will contain : -, +, *, /, % ,(, ) )
I will go char by char on the input string. Every time I find a number I will push it into Numbers, every time I find an operator or '(' I will push it into the Operators Stack. Every time I find a ')' I will extract from the Numbers and from the Operators Stack until I meet '('. I will evaluate the expression got , and insert the result into the Numbers Stack.
After I am done evaluating the input, I will go through my stack and compute the expression that now has no parentheses.
Q: How will I evaluate an expression that doesn't contain parentheses?
A: I will do it in a function like : public int evaluateExp(String exp){...}
- I will use 2 stacks: num and op (^_^)
- in num I will insert all the numbers I meet in the exp
- in op I will insert all the operators I meet in the exp, but every time I meet * or / or % I will extract the last number pushed in the num , I will get the next number that appears in the exp and compute the operation with the current operator I have. Next, insert the result into numbers and continue evaluating the exp.
- when I have just one number into the numberStack and I am done evaluating the exp , I will return the head of the numberStack.
And Done!
@ kamy : r u taking care of operator precedancy ?
Ex : 5+(3*4+5) , 5+(3+4*5) .. u follow the same procedure for these two ..
and also u'r algo fails if it doesn't contain any paranthesis ..
Ex: 5+6
yes I am taking care of operator precedency :
I have 2 functions :
1) int computeWholeExp(String input)
- gets the input , puts the numbers in Stack N and operators and parentheses in Stack O.
- every time we find ')' we extract in two temporary stacks num and op all the numbers and operators until I pop I '(' , which I will not put in op.
- will call evaluateExp(num, op) and put the result into N.
- go forward in the input and repeat the previous steps if needed
- when we finished the input we will call evaluateExp(N, O)
and return the result.
2) evaluateExp(Stack n, Stack op)
- also takes care of operator precedence and negative numbers
// We need this for the Stack class.
import java.util.*;
class ExprTreeNode {
ExprTreeNode left, right; // The usual pointers.
boolean isLeaf; // Is this a leaf?
int value; // If so, we'll store the number here.
char op; // If not, we need to know which operator.
}
class ExpressionTree {
ExprTreeNode root;
public void parseExpression (String expr)
{
root = parse (expr);
}
ExprTreeNode parse (String expr)
{
ExprTreeNode node = new ExprTreeNode ();
// Note: expr.charAt(0) is a left paren.
// First, find the matching right paren.
int m = findMatchingRightParen (expr, 1);
String leftExpr = expr.substring (1, m+1);
// Bottom-out condition:
if (m == expr.length()-1) {
// It's at the other end => this is a leaf.
String operandStr = expr.substring (1, expr.length()-1);
node.isLeaf = true;
node.value = getValue (operandStr);
return node;
}
// Otherwise, there's a second operand and an operator.
// Find the left paren to match the rightmost right paren.
int n = findMatchingLeftParen (expr, expr.length()-2);
String rightExpr = expr.substring (n, expr.length()-1);
// Recursively parse the left and right substrings.
node.left = parse (leftExpr);
node.right = parse (rightExpr);
node.op = expr.charAt (m+1);
return node;
}
int findMatchingRightParen (String s, int leftPos)
{
Stack<Character> stack = new Stack<Character>();
stack.push (s.charAt(leftPos));
for (int i=leftPos+1; i<s.length(); i++) {
char ch = s.charAt (i);
if (ch == '(') {
stack.push (ch);
}
else if (ch == ')') {
stack.pop ();
if ( stack.isEmpty() ) {
// This is the one.
return i;
}
}
}
// If we reach here, there's an error.
System.out.println ("ERROR: findRight: s=" + s + " left=" + leftPos);
return -1;
}
int findMatchingLeftParen (String s, int rightPos)
{
Stack<Character> stack = new Stack<Character>();
stack.push (s.charAt(rightPos));
for (int i=rightPos-1; i>=0; i--) {
char ch = s.charAt (i);
if (ch == ')') {
stack.push (ch);
}
else if (ch == '(') {
stack.pop ();
if ( stack.isEmpty() ) {
// This is the one.
return i;
}
}
}
// If we reach here, there's an error.
System.out.println ("ERROR: findLeft: s=" + s + " right=" + rightPos);
return -1;
}
int getValue (String s)
{
try {
int k = Integer.parseInt (s);
return k;
}
catch (NumberFormatException e) {
return -1;
}
}
public int computeValue ()
{
return compute (root);
}
int compute (ExprTreeNode node)
{
if (node.isLeaf) {
return node.value;
}
// Otherwise do left and right, and add.
int leftValue = compute (node.left);
int rightValue = compute (node.right);
if (node.op == '+') {
return leftValue + rightValue;
}
else if (node.op == '-') {
return leftValue - rightValue;
}
else if (node.op == '*') {
return leftValue * rightValue;
}
else {
return leftValue / rightValue;
}
}
public String convertToPostfix ()
{
String str = postOrder (root);
return str;
}
String postOrder (ExprTreeNode node)
{
String result = "";
if (node.left != null) {
result += postOrder (node.left);
}
if (node.right != null) {
result += " " + postOrder (node.right);
}
if (node.isLeaf) {
result += " " + node.value;
}
else {
result += " " + node.op;
}
return result;
}
}
class PostfixEvaluator {
public int compute (String postfixExpr)
{
// Create a stack: all our operands are integers.
Stack<Integer> stack = new Stack<Integer>();
// Use the Scanner class to help us extract numbers or operators:
Scanner scanner = new Scanner (postfixExpr);
while (scanner.hasNext()) {
if (scanner.hasNextInt()) {
// It's an operand => push it on the stack.
int N = scanner.nextInt();
stack.push (N);
}
else {
// It's an operator => apply the operator to the top two operands
String opStr = scanner.next();
int b = stack.pop(); // Note: b is popped first.
int a = stack.pop();
if (opStr.equals("+")) {
stack.push (a+b);
}
else if (opStr.equals("-")) {
stack.push (a-b);
}
else if (opStr.equals("*")) {
stack.push (a*b);
}
else if (opStr.equals("/")) {
stack.push (a/b);
}
}
} // end-while
// Result is on top.
return stack.pop();
}
}
public class ExpressionParser {
public static void main (String[] argv)
{
String s = "((1)+(2))";
test (s);
s = "(((1)+(2))*(3))";
test (s);
s = "(((35)-((3)*((3)+(2))))/(4))";
test (s);
}
static void test (String s)
{
ExpressionTree expTree = new ExpressionTree ();
expTree.parseExpression (s);
int v = expTree.computeValue ();
System.out.println (s + " = " + v);
String postStr = expTree.convertToPostfix ();
PostfixEvaluator postfixEval = new PostfixEvaluator();
int p = postfixEval.compute (postStr);
System.out.println ("Postfix: " + postStr + " postfix eval=" + p);
}
}
it works without parenthesis ....
- omkumarbitsindri December 13, 2012public class MainCalc {
public static void main(String[] args) {
System.out.println("Enter Expression:");
Scanner scan=new Scanner(System.in);
String equation=scan.next();
//String equation="(2*3)/5"; //MY CHALLENGE
//System.out.println(equation);
String answer=equation;
Operation opcode=new Operation();
StringTokenizer sto=new StringTokenizer(equation, "0123456789");
StringBuffer sbuf=new StringBuffer();
while (sto.hasMoreTokens()) {
sbuf.append(sto.nextToken());
}
String opcheck =sbuf.toString();
if(opcheck.contains("(")){
}
if(opcheck.contains("/")){
opcode.divMethod(equation);
answer= opcode.resultFinal;
// System.out.println(answer);
}
if(opcheck.contains("*")){
//
// System.out.println(answer);
opcode.multMethod(answer);
answer=opcode.resultFinal;
// System.out.println(answer);
}
if(opcheck.contains("+")){
opcode.plusMethod(answer);
answer=opcode.resultFinal;
}
if(opcheck.contains("-")){
opcode.minusMethod(answer);
answer=opcode.resultFinal;
}
System.out.println(answer);
}
}
public class Operation {
public String resultFinal;
public void divMethod( String string){
StringTokenizer sto=new StringTokenizer(string, "+-*/");
int lenght=0;
while(sto.hasMoreTokens()){
sto.nextToken();
lenght++;
}
if(lenght==1){}
else{
int [] numberlist=new int[lenght];
StringTokenizer stnk=new StringTokenizer(string,"+-*/");
int i=0;
while(stnk.hasMoreTokens()){
numberlist[i]=Integer.parseInt(stnk.nextToken());
i++;
}
StringBuffer strbuf=new StringBuffer();
StringTokenizer stoken=new StringTokenizer(string, "[0123456789]");
while(stoken.hasMoreElements()){
strbuf.append(stoken.nextToken());
}
for(int k=0;k<1;k++){
int divindexfield=string.indexOf("/");
if(divindexfield!=-1){
int indexof=strbuf.indexOf("/");
// System.out.println(strbuf);
// System.out.println(indexof);
int temp=numberlist[indexof++]/numberlist[indexof];
indexof--;
int firstlenght=String.valueOf(numberlist[indexof++]).length();
int secondlengh=String.valueOf(numberlist[indexof]).length();
StringBuffer stb=new StringBuffer();
stb.append(string);
stb.replace(divindexfield-firstlenght,divindexfield+secondlengh+1,String.valueOf(temp) );
String finalnewstring="";
finalnewstring=stb.toString();
resultFinal=finalnewstring;
// System.out.println(finalnewstring);
divMethod(finalnewstring);
}
}
}
}
public void multMethod( String string){
StringTokenizer sto=new StringTokenizer(string, "+-*/");
int lenght=0;
while(sto.hasMoreTokens()){
sto.nextToken();
lenght++;
}
if(lenght==1){}
else{
StringTokenizer strtok=new StringTokenizer(string, "+-*/");
int i=0;
int [] numberarray=new int[lenght];
while(strtok.hasMoreTokens()){
//System.out.println(strtok.nextToken());
numberarray[i]=Integer.parseInt(strtok.nextToken());
i++;
}
StringBuffer strbuf=new StringBuffer();
StringTokenizer strtoken=new StringTokenizer(string, "[0123456789]");
while(strtoken.hasMoreTokens()){
strbuf.append(strtoken.nextToken());
}
for(int k=0;k<1;k++){
int multindex=string.indexOf("*");
// System.out.println(multindex);
if(multindex!=-1){
int index=strbuf.indexOf("*");
int temp=numberarray[index++]*numberarray[index];
index--;
// System.out.println(strbuf);
int firststring=String.valueOf(numberarray[index++]).length();
// System.out.println(firststring);
int secondstring=String.valueOf(numberarray[index]).length();
//System.out.println(secondstring);
StringBuffer b=new StringBuffer();
b.append(string);
b.replace(multindex-firststring, multindex+secondstring+1, String.valueOf(temp));
String Finalstring="";
Finalstring=b.toString();
// System.out.println(Finalstring);
resultFinal =Finalstring;
multMethod(Finalstring);
}
}
}
}
public void minusMethod( String string){
StringTokenizer stkn = new StringTokenizer(string, "+-*/");
int length = 0;
while(stkn.hasMoreTokens()){
stkn.nextToken();
length++;
}
if(length==1){
}
else{
int[] numbersList = new int[length];
StringTokenizer noToken = new StringTokenizer(string, "-/*+");
int i=0;
while(noToken.hasMoreTokens()){
numbersList[i] = Integer.parseInt(noToken.nextToken());
i++;
}
StringBuffer noop = new StringBuffer();
StringTokenizer noOp = new StringTokenizer(string, "[0123456789]");
while(noOp.hasMoreTokens()){
noop.append(noOp.nextToken());
}
for(int k=0;k<1;k++){
int divIndexFind = string.indexOf("-");
if(divIndexFind!=-1){
int indexOp = noop.indexOf("-");
int temp = numbersList[indexOp++]-numbersList[indexOp];
indexOp--;
int firstLength = String.valueOf(numbersList[indexOp++]).length();
int secondLength = String.valueOf(numbersList[indexOp]).length();
StringBuffer b = new StringBuffer();
b.append(string);
b.replace(divIndexFind-firstLength,divIndexFind+secondLength+1, String.valueOf(temp));
String finalNewString = "";
finalNewString = b.toString();
resultFinal = finalNewString;
minusMethod(finalNewString);
}
}
}
}
public void plusMethod( String string){
StringTokenizer stkn = new StringTokenizer(string, "+-*/");
int length = 0;
while(stkn.hasMoreTokens()){
stkn.nextToken();
length++;
}
if(length==1){
}
else{
int[] numbersList = new int[length];
StringTokenizer noToken = new StringTokenizer(string, "-/*+");
int i=0;
while(noToken.hasMoreTokens()){
numbersList[i] = Integer.parseInt(noToken.nextToken());
i++;
}
StringBuffer noop = new StringBuffer();
StringTokenizer noOp = new StringTokenizer(string, "[0123456789]");
while(noOp.hasMoreTokens()){
noop.append(noOp.nextToken());
}
for(int k=0;k<1;k++){
int divIndexFind = string.indexOf("+");
if(divIndexFind!=-1){
int indexOp = noop.indexOf("+");
int temp = numbersList[indexOp++]+numbersList[indexOp];
indexOp--;
int firstLength = String.valueOf(numbersList[indexOp++]).length();
int secondLength = String.valueOf(numbersList[indexOp]).length();
StringBuffer b = new StringBuffer();
b.append(string);
b.replace(divIndexFind-firstLength,divIndexFind+secondLength+1, String.valueOf(temp));
String finalNewString = "";
finalNewString = b.toString();
resultFinal = finalNewString;
plusMethod(finalNewString);
}
}
}
}
}