Amazon Interview Question SDE1s
Team: DSV QA team
Country: India
Interview Type: Phone Interview
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void evaluateExpression(String s)
{
char mul = '*';
char div ='/';
char add = '+';
char sub = '-';
ArrayList<String> list = new ArrayList<String>();
char []a = s.toCharArray();
StringBuilder sb = new StringBuilder();
int divPos=0,mulPos=0,addPos=0,subPos=0;
for(int i=0;i<a.length;i++)
{
boolean isOperator = (a[i] == mul || a[i] == div || a[i] == sub || a[i] == add)?true:false;
if(isOperator)
{
list.add(sb.toString());
String text = String.valueOf(a[i]);
list.add(text);
sb = new StringBuilder();
}
else
{
sb.append(a[i]);
}
}
list.add(sb.toString());
for(int i=0;i<list.size();i++)
{
String op =list.get(i);
if(op.equals(String.valueOf(div)))
{
divPos = i;
}
else if(op.equals(String.valueOf(mul)))
{
mulPos = i;
}
}
System.out.println(" "+list.toString());
int q = Integer.valueOf(list.get(divPos-1));
int d = Integer.valueOf(list.get(divPos+1));
int ans = (int)q/d;
list.add(divPos-1,String.valueOf(ans));
list.subList(divPos,divPos+3).clear();
q = Integer.valueOf(list.get(mulPos-1));
d = Integer.valueOf(list.get(mulPos+ 1));
ans = q*d;
list.add(mulPos-1,String.valueOf(ans));
list.subList(mulPos,mulPos+3).clear();
System.out.println(" "+list.toString());
for(int i=0;i<list.size();i++)
{
String op =list.get(i);
if(op.equals(String.valueOf(add)))
{
addPos = i;
}
}
q = Integer.valueOf(list.get(addPos-1));
d = Integer.valueOf(list.get(addPos+ 1));
ans = q+d;
list.add(addPos-1,String.valueOf(ans));
list.subList(addPos,addPos+3).clear();
System.out.println(" "+list.toString());
subPos = list.size()-2;
q = Integer.valueOf(list.get(subPos-1));
d = Integer.valueOf(list.get(subPos+ 1));
ans = q+d;
list.add(subPos-1,String.valueOf(ans));
list.subList(subPos,subPos+3).clear();
System.out.println(" "+list.toString());
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
evaluateExpression("3+12*3-4/7");
}
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void evaluateExpress(String in)
{
Stack<String> operator = new Stack<String>();
Stack<String> value = new Stack<String>();
StringBuilder sb = new StringBuilder();
char[] input = in.toCharArray();
//3+12*3-4/7
for(int i=0;i<input.length;i++)
{
String s = String.valueOf(input[i]);
if( isOperator(s))
{
value.push(sb.toString());
sb = new StringBuilder();
if(operator.isEmpty())
{
operator.push(s);
}
else
{
String temp = operator.peek();
boolean isHighPrecedence = precedenceHigh(s,temp);
if(isHighPrecedence)
{
int a = Integer.valueOf(value.pop());
int b = Integer.valueOf(value.pop());
int ans = evaluate(b,a,temp);
value.push(String.valueOf(ans));
operator.pop();
operator.push(s);
}
else
{
operator.push(s);
}
}
}
else
{
sb.append(input[i]);
}
}
value.push(sb.toString());
System.out.println( " size "+operator.size());
while(!operator.isEmpty())
{
String temp = operator.pop();
int a = Integer.valueOf(value.pop());
int b = Integer.valueOf(value.pop());
int ans = evaluate(b,a,temp);
value.push(String.valueOf(ans));
}
System.out.println( " operator "+operator.toString());
System.out.println( " value "+value.toString());
}
public static int evaluate(int a,int b,String c)
{
if(c.equals("/"))
{
return (a/b);
}
else if(c.equals("*"))
{
return (a*b);
}
else if(c.equals("+"))
{
return (a+b);
}
else if(c.equals("-"))
{
return (a-b);
}
return -1;
}
public static boolean precedenceHigh(String a,String b)
{
if(b.equals("/") || b.equals("*"))
return true;
return false;
}
public static boolean isOperator(String a)
{
if(a.equals("*") || a.equals("+") || a.equals("-") || a.equals("/"))
{
return true;
}
return false;
}
public static boolean isValue(String a)
{
String pattern = "(\\d+)";
Pattern r = Pattern.compile(pattern);
Matcher m = r.matcher(a);
if(m.find()) return true;
return false;
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
//System.out.println(isValue("12"));
//System.out.println(isValue("2"));
evaluateExpress("3+12*3-4/7");
}
}
public class ArithRPNEval {
public static void main(String[] args) {
String input = "11+12*2+20/2/2+1";
int len = input.length();
List<String> tokens = new ArrayList<String>();
// can be better done with regular expression
int offset = 0;
for(int i = 0; i < len; i++) {
char c = input.charAt(i);
if (c == '+' || c == '-' || c == '*' || c == '/') {
tokens.add(input.substring(offset, i));
offset = i + 1;
tokens.add(String.valueOf(c));
}
}
tokens.add(input.substring(offset, input.length()));
List<String> done = new ArrayList<String>();
List<String> buffer = new ArrayList<String>();
for(String token : tokens) {
Operator op = getOperator(token);
if (op == null) {
done.add(token);
} else {
flush(buffer, done, op.priority);
buffer.add(token);
}
}
flush(buffer, done, 0);
String ret = eval(done);
System.out.println(ret);
}
private static String eval(List<String> done) {
List<String> pending = new ArrayList<String>();
for(int i = 0; i < done.size(); i++) {
String token = done.get(i);
Operator op = getOperator(token);
if (op == null) {
pending.add(token);
} else {
String operand2 = pending.remove(pending.size() - 1);
String operand1 = pending.remove(pending.size() - 1);
int value = 0;
if (op == Operator.PLUS) {
value = Integer.valueOf(operand1) + Integer.valueOf(operand2);
} else if (op == Operator.MINUS) {
value = Integer.valueOf(operand1) - Integer.valueOf(operand2);
} else if (op == Operator.MUL) {
value = Integer.valueOf(operand1) * Integer.valueOf(operand2);
} else if (op == Operator.DIV) {
value = Integer.valueOf(operand1) / Integer.valueOf(operand2);
}
pending.add(String.valueOf(value));
}
}
return pending.get(0);
}
private static void flush(List<String> buffer, List<String> done,
int priority) {
while(buffer.size() > 0) {
Operator op = getOperator(buffer.get(buffer.size() - 1));
if (op.priority >= priority) {
done.add(op.s);
buffer.remove(buffer.size() - 1);
} else {
break;
}
}
}
private static Operator getOperator(String token) {
if ("+".equals(token)) {
return Operator.PLUS;
} else if ("-".equals(token)) {
return Operator.MINUS;
} else if ("*".equals(token)) {
return Operator.MUL;
} else if ("/".equals(token)) {
return Operator.DIV;
}
return null;
}
static enum Operator {
PLUS(1, "+"), MINUS(2, "-"), MUL(3, "*"), DIV(4, "/");
int priority;
String s;
Operator(int priority, String s) {
this.priority = priority;
this.s = s;
}
}
}
Here's solution in C++.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
static int precedence(char x) //check precedence of operators
{
if(x=='(')
return 0;
else if(x=='+'||x=='-')
return 1;
else if(x=='*'||x=='/'||x=='%')
return 2;
return 3;
}
std::string infix_to_postfix(const std::string& infix)
{
std::stack<char> s;
std::string postfix;
for (auto ch : infix)
{
if (isalnum(ch))
postfix.push_back(ch);
else if (ch == '(')
s.push(ch);
else if(ch == ')')
{
while (!s.empty())
{
ch = s.top();
s.pop();
if (ch == '(')
break;
postfix.push_back(ch);
}
}
else
{
while(!s.empty() && precedence(ch)<=precedence(s.top()))
{
postfix.push_back(s.top());
s.pop();
}
s.push(ch);
}
}
while(!s.empty())
{
postfix.push_back(s.top());
s.pop();
}
return postfix;
}
int main()
{
const char infix[] = "3+12*3-4/7";
cout << "\nThe equivalent postfix expression is: " << infix_to_postfix(infix);
return 0;
Ans:
The equivalent postfix expression is: 3123*+47/-
I convert the input expression in a postfix expression, represented with a List<String>.
Then I push this postfix version into a Stack starting from the last element of the postfix expression.
To evaluate the postfix expression inserted into a stack I pop elements and push them into an helper stack until I find an operator. When I find an operator in the Stack of the postfix expression I pop 2 elements from the helper stack and apply the operator to thos two elements. then push back the result of this operation to the helper stack. Keep going until the stack with the postfix expression will be empty. At the end you will have the result in the helper stack.
Here is the code to implement this solution, the method
List<String> getExpressionTokens(String s)
convert the input expression string into single tokens and the method
List<String> toPostfix(String s)
convert an input infix expression String into a postfix expression.
Those two previous methods are used in the method
String eval(String s)
that evaluate an expression and retrieve the result in a String.
Here is the complete code for this solution:
import java.util.*;
public class EvaluateExpression {
public static List<String> toPostfix(String s) {
List<String> postfix = new ArrayList<String>();
Map<String,Integer> operators = new HashMap<String,Integer>();
operators.put("*", 1);
operators.put("/", 1);
operators.put("+", 2);
operators.put("-", 2);
List<String> tokens = getExpressionTokens(s);
Stack<String> stack = new Stack<String>();
for(String token: tokens) {
if(operators.containsKey(token)) {
if(stack.size()==0) {
stack.push(token);
}
else {
while(stack.size()>0 && operators.get(stack.peek())<=operators.get(token)) {
postfix.add(stack.pop());
}
stack.push(token);
}
}
else {
postfix.add(token);
}
}
while(stack.size()>0) {
postfix.add(stack.pop());
}
return postfix;
}
public static List<String> getExpressionTokens(String s) {
List<String> tokens = new ArrayList<String>();
String token = "";
Set<Character> operators = new HashSet<Character>();
operators.add('*');
operators.add('/');
operators.add('+');
operators.add('-');
for(int i=0;i<s.length();i++) {
if(!operators.contains(s.charAt(i))) {
token+=s.charAt(i);
}
else {
tokens.add(token);
tokens.add(String.valueOf(s.charAt(i)));
token = "";
}
}
if(token.length()>0) {
tokens.add(token);
}
return tokens;
}
public static String eval(String s) {
List<String> expr = toPostfix(s);
Set<String> operators = new HashSet<String>();
operators.add("*");
operators.add("/");
operators.add("+");
operators.add("-");
Stack<String> postfix = new Stack<String>();
Stack<String> helper = new Stack<String>();
for(int i=expr.size()-1;i>=0;i--) {
postfix.push(expr.get(i));
}
String token = "";
while(postfix.size()>0) {
token = postfix.pop();
if(operators.contains(token)) {
String el1 = helper.pop();
String el2 = helper.pop();
if(token.equals("*")) {
helper.push(String.valueOf(Double.valueOf(el2)*1.0*Double.valueOf(el1)));
}
if(token.equals("/")) {
helper.push(String.valueOf(Double.valueOf(el2)/1.0/Double.valueOf(el1)));
}
if(token.equals("+")) {
helper.push(String.valueOf(Double.valueOf(el2)+0.0+Double.valueOf(el1)));
}
if(token.equals("-")) {
helper.push(String.valueOf(Double.valueOf(el2)-0.0-Double.valueOf(el1)));
}
}
else {
helper.push(token);
}
}
if(helper.size()>0) {
return helper.pop();
}
else return "0";
}
public static void main(String[] args){
String expr = "12*3-4+2*8";
//System.out.println(expr);
//System.out.println(getExpressionTokens(expr));
//List<String> postfix = toPostfix(expr);
//System.out.println(postfix);
System.out.println(expr+" = "+eval(expr));
}
}
public class Hello {
public static void main(String[] args) {
String expression="3+12*3*3-4/7";
String[] subArray= expression.split("-");
int subVal=addVal(subArray[0]);
for (int i = 1; i <subArray.length ; i++) {
subVal=subVal-addVal(subArray[i]);
}
System.out.println(subVal);
}
static int mulVal(String add)
{
String[] mulArray=add.split("\\*");
int val=1;
for (int i = 0; i <mulArray.length ; i++) {
val*=divVal(mulArray[i]);
}
return val;
}
static int addVal(String sub)
{
String[] addArray=sub.split("\\+");
int val=0;
for (int i = 0; i <addArray.length ; i++) {
val+=mulVal(addArray[i]);
}
return val;
}
static int divVal(String mul)
{
String[] divArray=mul.split("/");
int val=1;
if(divArray.length==1)
{
val=Integer.parseInt(divArray[0]);
}
else
{
val=Integer.parseInt(divArray[0])/Integer.parseInt(divArray[1]);
}
return val;
}
}
package com.abdul.az;
import java.util.Stack;
public class Problems {
enum Operation {
PLUS('+'), MINUS('-'), MULTIPLY('*'), DIVIDE('/');
char operation;
Operation(char operation) {
this.operation = operation;
}
int getValue(int a, int b) {
if (operation == '+') {
return a + b;
} else if (operation == '-') {
return a - b;
} else if (operation == '/') {
return a / b;
} else if (operation == '*') {
return a * b;
}
throw new RuntimeException("Invalid operation");
}
public static Operation getOperation(char c) {
for (Operation op : Operation.values()) {
if (op.operation == c) {
return op;
}
}
throw new RuntimeException("Invalid Operation for :" + c);
}
};
public static void main(String[] args) {
// pairsForTwoIntegerArrays();
mathmeticalExpression("2+2+4+4");
}
private static void mathmeticalExpression(String string) {
int countTotal = 0;
boolean initialFetch = true;
for (int i = 0; i < string.length(); i++) {
char c = string.charAt(i);
if (initialFetch) {
int arg1 = Character.getNumericValue(string.charAt(i));
int arg2 = Character.getNumericValue(string.charAt(i + 2));
countTotal = Operation.getOperation(string.charAt(i + 1))
.getValue(arg1, arg2);
i += 2;
initialFetch = false;
} else {
int arg2 = Character.getNumericValue(string.charAt(i + 1));
countTotal = Operation.getOperation(string.charAt(i)).getValue(
countTotal, arg2);
i += 1;
}
}
System.out.println("*********** Total:" + countTotal);
}
}
-Create tokens from strings for numbers and signs
-Calculate all multiplications and division
-Calculate all plus minus from result of above
Code:
import java.util.ArrayList;
public class Calculation {
private String str = null;
public String resStr = null;
public String getStr() {
return str;
}
public void setStr(String str) {
this.str = str;
}
public ArrayList Tokenization() {
int i = this.getStr().length();
int j = 0, l = 0;
ArrayList al = new ArrayList();
int si = 0;
if (i == 0) {
System.out.println("No String Passed");
System.exit(0);
} else {
while (j < i) {
// System.out.println("-->" + this.getStr().charAt(j));
l = Character.getNumericValue((char) this.getStr().charAt(j));
if (this.getStr().charAt(j) == '+'
|| this.getStr().charAt(j) == '-'
|| this.getStr().charAt(j) == '*'
|| this.getStr().charAt(j) == '/') {
al.add(this.getStr().substring(si, j));
al.add(this.getStr().charAt(j));
si = j + 1;
}
else if (l > 9 || l < 0) {
System.out.println("==>" + this.getStr().charAt(j));
System.out.println(" encountered...");
System.out.println("Wrong Input...");
System.out.println("Exiting...");
System.exit(1);
}
j++;
}
al.add(this.getStr().substring(si, j));
}
if ("".equals(al.get(0))) {
al.set(0, 0);
}
return al;
}
public ArrayList calculateMultDevide(ArrayList al, int index) {
int length = al.size();
int i = 0, j = 0;
for (i = index; i < length - 1; i = i + 2) {
if ("*".equals(al.get(i).toString())) {
System.out.println("visited *");
j = i - 1;
while (al.get(j) == null) {
j = j - 2;
}
al.set(i + 1,
(Integer.parseInt(al.get(i + 1).toString()) * Integer
.parseInt(al.get(j).toString())));
al.set(i, null);
al.set(i - 1, null);
if (i + 2 < (length - 1)) {
al = this.calculateMultDevide(al, i + 2);
break;
}
}
else if ("/".equals(al.get(i).toString())) {
System.out.println("visited /");
j = i - 1;
while (al.get(j) == null) {
j = j - 2;
}
al.set(i + 1, (Integer.parseInt(al.get(j).toString()) / Integer
.parseInt(al.get(i + 1).toString())));
al.set(i, null);
al.set(j, null);
if (i + 2 < (length - 1)) {
al = this.calculateMultDevide(al, i + 2);
break;
}
}
}
return al;
}
public int calculatePlusMinus(ArrayList arl) {
int total = 0;
int i = 0;
int flag = 0;
int length = arl.size();
while (i < length - 1) {
while (arl.get(i) == null) {
i++;
}
if (i % 2 == 0) {
if (flag == 0) {
total = total + Integer.parseInt(arl.get(i).toString());
} else {
total = total - Integer.parseInt(arl.get(i).toString());
}
}
if (i % 2 != 0) {
if ("-".equals(arl.get(i).toString())) {
flag = 1;
} else {
flag = 0;
}
}
i++;
}
return total;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int total = 0;
Calculation cal = new Calculation();
cal.setStr("333-1+23*566*1-9/2*2*3");
// cal.setStr("");
ArrayList arl = cal.Tokenization();
int length = arl.size();
int i = 0;
for (i = 0; i < length; i++) {
System.out.println("arl--" + i + "-->" + (arl.get(i)).toString());
}
if (arl.size() == 1) {
System.out.println("No Calculation Required: "
+ (arl.get(0)).toString());
}
else {
arl = cal.calculateMultDevide(arl, 1);
for (i = 0; i < length; i++) {
System.out.println("arl--" + i + "-->" + (arl.get(i)));
}
total = cal.calculatePlusMinus(arl);
System.out.println("Result is: " + total);
}
}
}
Answer is simple, maintain priority list top priority list store mul,div operator at next priority store +,_ operator,now scan through the given linklist or whatever it is at first level scanning resolve highest priority operator ,whereever encounter remove its left right node and now add the answer at this node. and continue... similarly for next prioirity operators..
R
str <- "3+12*3-4/7-12*2/2"
op <- c('/','*','-','+')
str1 <- as.numeric(strsplit(gsub("[+-/*]",",",str),',')[[1]])
str2 <- strsplit(str,"")[[1]]
str3 <- op[match(str2,op)[!is.na(match(str2,op))]]
str4 <- rep(NA, length(str1) + length(str3))
str4[seq(1, length(str4), by = 2)] <- str1
str4[is.na(str4)] <- str3
str2a <- str4
# multiplcation and division
md <- function(str2a) {
i <-1
while(length(str2a)>1){
if(str2a[i] == '*'){
str2a[i] <- as.numeric(str2a[i-1]) * as.numeric(str2a[i+1])
str2a <- str2a[-c(i-1,i+1)]
} else if(str2a[i] == '/'){
str2a[i] <- as.numeric(str2a[i-1]) / as.numeric(str2a[i+1])
str2a <- str2a[-c(i-1,i+1)]
}
i <- i +1
if(i > length(str2a)) {i <- 1}
if(length(which(str2a %in% op[1:2])) == 0){break}
}
return(str2a)
}
str2b <- md(str2a)
as <- function(str2a){
i <-1
while(length(str2a)>1){
if(str2a[i] == '+'){
str2a[i] <- as.numeric(str2a[i-1]) + as.numeric(str2a[i+1])
str2a <- str2a[-c(i-1,i+1)]
} else if(str2a[i] == '-'){
str2a[i] <- as.numeric(str2a[i-1]) - as.numeric(str2a[i+1])
str2a <- str2a[-c(i-1,i+1)]
}
i <- which(str2a %in% op[3:4])[1]
if(length(which(str2a %in% op[3:4])) == 0){break}
}
return(as.numeric(str2a))
}
as(str2b)
struct calcNode{
int type;// +- or */
double number;
};
vector<calcNode> expression;
double number;
char operator;
int count;
while( (count = scanf("%d%c[+-*/]",&number, &operator)) != 0 )
{
char *a = "+-*/";
for(size_t i = 0;i<4;i++)
if(a[i] == operator)
operator = i;
expression.push( calcNode(type, number) )
if(count == 1)
break;
}
size_t i = 0;
size_t k = 0;
for(;i<expression.size()-1;i++){
if(expression[i].type >= 2){
if(expression[i].type == 2)
expression[i+k+1].number = expression[i].number * expression[i+k+1].number;
else
expression[i+k+1].number = expression[i].number / expression[i+k+1].number;
expression[i] = expression[i+k+1];
k++;
}
}
expression.resize(expression.size()-k);
i = k = 0;
for(;i<expression.size()-1;i++){
if(expression[i].type < 2){
if(expression[i].type == 0)
expression[i+k+1].number = expression[i].number + expression[i+k+1].number;
else
expression[i+k+1].number = expression[i].number - expression[i+k+1].number;
expression[i] = expression[i+k+1];
k++;
}
}
expression.resize(expression.size()-k);
double finalResult = expression[0].number;
C++ solution with operand and operator stack
#include <map>
#include <sstream>
#include <stdio.h>
#include <string>
#include <stack>
using namespace std;
double GetNum(stringstream &ss) {
double v;
ss >> v;
return v;
}
char GetOp(stringstream &ss) {
char c;
ss >> c;
return c;
}
void Calc(stack<char> &ops, stack<double> &nums) {
double v2 = nums.top();
nums.pop();
double v1 = nums.top();
nums.pop();
double res;
switch (ops.top()) {
case '+': res = v1+v2; break;
case '-': res = v1-v2; break;
case '*': res = v1*v2; break;
case '/': res = v1/v2; break;
};
nums.push(res);
ops.pop();
}
double EvalExpressionString(const string &e) {
const map<char, int> op_prec{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
stack<double> nums;
stack<char> ops;
stringstream ss(e);
// add first number
nums.push(GetNum(ss));
while (!ss.eof()) {
char next_op = GetOp(ss);
// calc all ops in stack with higher precedence than next op
while (!ops.empty() && op_prec.at(ops.top()) > op_prec.at(next_op))
Calc(ops, nums);
ops.push(next_op);
nums.push(GetNum(ss));
}
// calc remaining ops
while (!ops.empty())
Calc(ops, nums);
return nums.top();
}
int main() {
printf("%f\n", EvalExpressionString("3+12*3-4/7"));
printf("%f\n", EvalExpressionString("3+2*2*3-1"));
}
import javax.script.ScriptEngineManager;
import javax.script.ScriptEngine;
public class EvaluateExpression {
public static void main(String[] args) throws Exception{
ScriptEngineManager mgr = new ScriptEngineManager();
ScriptEngine engine = mgr.getEngineByName("JavaScript");
String foo = "3+12*3-4/7";
System.out.println(engine.eval(foo));
}
}
Convert the given infix expression ("3+12*3-4/7") to postfix (3 12 3 * + 4 7 / -).
- sumanth232 December 24, 2014Here is the algorithm and code to do so http://geeksquiz.com/stack-set-2-infix-to-postfix/
The postfix expressions can be evaluated very easily using a stack