Epic Systems Interview Question Software Engineer / Developers
Country: United States
Interview Type: Written Test
There is no need to overcomplicate things with stacks.
At any given point in time, you have at most the following:
- Previous result
- Operator
So just store each in a single variable and update them as you parse the input string.
The only work you need to do is when a number is encountered, see if an operator has been defined. If so, calculate [previous result] [operator] [number], set this to previous result and clear the operator.
It may seem like it's overcomplicating things at first, but the standard way of doing these kinds of problems involve the stack method as it gives a better range of possibilities if we want to expand the problem to take into account, for instance, order of ops, or even parenthetical expressions.
Your solution is definitely more simple, be more space efficient, and just as correct, don't get me wrong, but the stack method gives us more to discuss with a potential interviewer and serves as a good model to understand for a lot of problems similar to this (see checking balanced parentheses problem for example).
import java.util.Stack;
public class OperatorEvaluation {
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack<String> OpStack = new Stack();
Stack<Integer> NumStack = new Stack();
int result = 0;
System.out.println("Enter an expression with numbers and operators *-+");
System.out.println("Operates left to right");
String test ="3+4*6-9";
StringBuffer sb = new StringBuffer(test);
char[] chars = (sb.reverse()).toString().toCharArray();
for(int i=0; i<chars.length ;i++)
{
if(chars[i]=='*' || chars[i]=='-' || chars[i]=='+')
{
OpStack.push(Character.toString(chars[i]));
}
else
{
NumStack.push(Integer.parseInt(Character.toString(chars[i])));
}
}
while(!OpStack.isEmpty() )
{
String op = OpStack.pop();
char c = op.charAt(0);
int a = NumStack.pop();
int b = NumStack.pop();
if(c == '*')
result = a*b;
if(c== '+')
result = (a+b);
if(c == '-')
result = (a-b);
NumStack.push(result);
}
System.out.println(result);
}
}
Thank you, Shriram! The codes are pretty good. if test ="13+4*6-9",it'll be a problem. "13" are two chars. how to solve this problem? Thanks.
import java.util.Stack;
public class OperatorEvaluation {
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack<String> OpStack = new Stack<String>();
Stack<Integer> NumStack = new Stack<Integer>();
int result = 0;
System.out.println("Enter an expression with numbers and operators *-+");
System.out.println("Operates left to right");
String test ="3+41*6-9*4";
StringBuffer sb = new StringBuffer(test);
char[] chars = (sb.reverse()).toString().toCharArray();
for(int i=0; i<chars.length ;i++)
{
if(chars[i]=='*' || chars[i]=='-' || chars[i]=='+')
{
OpStack.push(Character.toString(chars[i]));
}
else if(Character.isDigit(chars[i]))
{
String number = "";
int pushnumber;
while(Character.isDigit(chars[i]))
{
number += chars[i];
i++;
if( i > chars.length-1)
break;
}
StringBuffer buffer = new StringBuffer(number);
String push = (buffer.reverse()).toString();
pushnumber = Integer.parseInt(push);
NumStack.push(pushnumber);
i--;
}
else
break;
}
while(!OpStack.isEmpty() )
{
String op = OpStack.pop();
char c = op.charAt(0);
int a = NumStack.pop();
int b = NumStack.pop();
if(c == '*')
result = a*b;
if(c== '+')
result = (a+b);
if(c == '-')
result = (a-b);
NumStack.push(result);
}
System.out.println(result);
}
}
import java.util.Stack;
public class OperatorEvaluation {
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack<String> OpStack = new Stack();
Stack<Integer> NumStack = new Stack();
int result = 0;
System.out.println("Enter an expression with numbers and operators *-+");
System.out.println("Operates left to right");
String test ="3+4*6-9";
StringBuffer sb = new StringBuffer(test);
char[] chars = (sb.reverse()).toString().toCharArray();
for(int i=0; i<chars.length ;i++)
{
if(chars[i]=='*' || chars[i]=='-' || chars[i]=='+')
{
OpStack.push(Character.toString(chars[i]));
}
else
{
NumStack.push(Integer.parseInt(Character.toString(chars[i])));
}
}
while(!OpStack.isEmpty() )
{
String op = OpStack.pop();
char c = op.charAt(0);
int a = NumStack.pop();
int b = NumStack.pop();
if(c == '*')
result = a*b;
if(c== '+')
result = (a+b);
if(c == '-')
result = (a-b);
NumStack.push(result);
}
System.out.println(result);
}
}
Since the order of operations is just left to right we can just keep a running left to right total.
// Assumes a null terminated input string, integers values, and valid expression
int EvaluateString(char* inputString)
{
int currentTotal = GetNumber(inputString);
while (*inputString != '\0')
{
switch (*inputString)
{
case '*':
currentTotal *= GetNumber(++inputString);
break;
case '-':
currentTotal -= GetNumber(++inputString);
break;
case '+':
currentTotal += GetNumber(++inputString);
break;
default:
inputString++;
break;
}
}
return currentTotal;
}
int GetNumber(char* &inputString)
{
int currentNumber = 0;
int isPositive = 1;
if (*inputString == '-')
{
isPositive = -1;
inputString++;
}
while (*inputString >= '0' && *inputString <= '9')
{
// Multiply our current number by 10 and add the current parsed number
currentNumber = (currentNumber * 10) + (*inputString - '0');
inputString++;
}
return currentNumber * isPositive;
}
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> numStack = new ArrayList<Integer>();
ArrayList<Character> opStack = new ArrayList<Character>();
public void stackify(String str)
{
for(int i=0;i<str.length();i++)
{
String s = "";
if(str.charAt(i)>='0' &&str.charAt(i)<='9')
{
while(i < str.length() && str.charAt(i)>='0' && str.charAt(i)<='9')
{
s=s+str.charAt(i);
i++;
}
i--;
numStack.add(Integer.parseInt(s));
}
if(str.charAt(i)=='+' || str.charAt(i)=='-' || str.charAt(i)=='*'||str.charAt(i)=='/')
{
opStack.add(str.charAt(i));
}
}
}
public int evaluateString(String str)
{
stackify(str);
for(int i=0;i<opStack.size();i++)
{
int a = numStack.remove(0);
int b = numStack.remove(0);
int result=0;
char oper = opStack.get(i);
switch(oper)
{
case '+':result=a+b;
break;
case '-':result=a-b;
break;
case '*':result=a*b;
break;
case '/':result=a/b;
break;
}
numStack.add(0, result);;
}
return numStack.get(0);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Solution sol = new Solution();
String str = "34+4*6-9";
System.out.println(sol.evaluateString(str));
}
}
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> numStack = new ArrayList<Integer>();
ArrayList<Character> opStack = new ArrayList<Character>();
public void stackify(String str)
{
for(int i=0;i<str.length();i++)
{
String s = "";
if(str.charAt(i)>='0' &&str.charAt(i)<='9')
{
while(i < str.length() && str.charAt(i)>='0' && str.charAt(i)<='9')
{
s=s+str.charAt(i);
i++;
}
i--;
numStack.add(Integer.parseInt(s));
}
if(str.charAt(i)=='+' || str.charAt(i)=='-' || str.charAt(i)=='*'||str.charAt(i)=='/')
{
opStack.add(str.charAt(i));
}
}
}
public int evaluateString(String str)
{
stackify(str);
for(int i=0;i<opStack.size();i++)
{
int a = numStack.remove(0);
int b = numStack.remove(0);
int result=0;
char oper = opStack.get(i);
switch(oper)
{
case '+':result=a+b;
break;
case '-':result=a-b;
break;
case '*':result=a*b;
break;
case '/':result=a/b;
break;
}
numStack.add(0, result);;
}
return numStack.get(0);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Solution sol = new Solution();
String str = "34+4*6-9";
System.out.println(sol.evaluateString(str));
}
}
Simple program with O(1) memory requirement.
#include <iostream>
#include<string>
#include<cctype>
using namespace std;
int evaluate(char oper , int leftOp,int rightOp){
cout<<"Evaluate "<<leftOp<<" "<<oper<<" "<<rightOp<<endl;
int result;
switch(oper){
case '*' : result = leftOp * rightOp;
break;
case '+' : result = leftOp + rightOp;
break;
case '-' : result = leftOp - rightOp;
break;
}
return result;
}
int main() {
string expression = "3 * 4 + 8 - 9";
int leftOp , rightOp;
char oper ;
int i=0,k;
while((isdigit(expression[i]) or expression[i] == ' ') and i < expression.length())
i++;
leftOp = atoi(expression.substr(0,i).c_str());
while(i<expression.length())
{
k=i;
if(isdigit(expression[i]) or expression[i] == ' ' )
{
k = i;
while((isdigit(expression[k]) or expression[k] == ' ') and k < expression.length())
k++;
rightOp = atoi(expression.substr(i,k-i).c_str());
leftOp = evaluate(oper,leftOp,rightOp);
i = k-1;
}
else
oper = expression[i];
i++;
}
cout<<"Result = "<<leftOp<<endl;
return 0;
}
Simple program with O(1) space complexity
#include <iostream>
#include<string>
#include<cctype>
using namespace std;
int evaluate(char oper , int leftOp,int rightOp){
cout<<"Evaluate "<<leftOp<<" "<<oper<<" "<<rightOp<<endl;
int result;
switch(oper){
case '*' : result = leftOp * rightOp;
break;
case '+' : result = leftOp + rightOp;
break;
case '-' : result = leftOp - rightOp;
break;
}
return result;
}
int main() {
string expression = "3 * 4 + 8 - 9";
int leftOp , rightOp;
char oper ;
int i=0,k;
while((isdigit(expression[i]) or expression[i] == ' ') and i < expression.length())
i++;
leftOp = atoi(expression.substr(0,i).c_str());
while(i<expression.length())
{
k=i;
if(isdigit(expression[i]) or expression[i] == ' ' )
{
k = i;
while((isdigit(expression[k]) or expression[k] == ' ') and k < expression.length())
k++;
rightOp = atoi(expression.substr(i,k-i).c_str());
leftOp = evaluate(oper,leftOp,rightOp);
i = k-1;
}
else
oper = expression[i];
i++;
}
cout<<"Result = "<<leftOp<<endl;
return 0;
}
import java.util.Stack;
public class OperatorEvaluation {
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack<String> OpStack = new Stack<String>();
Stack<Integer> NumStack = new Stack<Integer>();
int result = 0;
System.out.println("Enter an expression with numbers and operators *-+");
System.out.println("Operates left to right");
String test ="3+41*6-9*4";
StringBuffer sb = new StringBuffer(test);
char[] chars = (sb.reverse()).toString().toCharArray();
for(int i=0; i<chars.length ;i++)
{
if(chars[i]=='*' || chars[i]=='-' || chars[i]=='+')
{
OpStack.push(Character.toString(chars[i]));
}
else if(Character.isDigit(chars[i]))
{
String number = "";
int pushnumber;
while(Character.isDigit(chars[i]))
{
number += chars[i];
i++;
if( i > chars.length-1)
break;
}
StringBuffer buffer = new StringBuffer(number);
String push = (buffer.reverse()).toString();
pushnumber = Integer.parseInt(push);
NumStack.push(pushnumber);
i--;
}
else
break;
}
while(!OpStack.isEmpty() )
{
String op = OpStack.pop();
char c = op.charAt(0);
int a = NumStack.pop();
int b = NumStack.pop();
if(c == '*')
result = a*b;
if(c== '+')
result = (a+b);
if(c == '-')
result = (a-b);
NumStack.push(result);
}
System.out.println(result);
}
}
import java.util.LinkedList;
public class EvaluateLeftToRight {
static LinkedList<Integer> numQueue = new LinkedList<Integer>();
static LinkedList<String> opQueue = new LinkedList<String>();
public static void main(String[] args) {
String expression = "3*4+5-9+6";
if(expression.length() == 0)
System.out.println("Empty String");
if(expression.length() == 1)
System.out.println(Integer.parseInt(expression));
splitExpression(expression); //method to split the input string into numbers and operators
int result = evaluateExpression(); //method to evaluate the expression
System.out.println(result);
}
public static void splitExpression(String expression) {
String number = "";
for(int i = 0; i < expression.length() - 1; i++) {
// Check if character is operator or digit, if it is a operator, add the operator to the queue
if(expression.charAt(i) == '-' || expression.charAt(i) == '+' || expression.charAt(i) == '*')
opQueue.add(String.valueOf(expression.charAt(i)));
// if the character is a digit
else {
number += expression.charAt(i);
//then check for the next character, if it is an operator, the number ends here
if(expression.charAt(i + 1) == '-' || expression.charAt(i + 1) == '+' || expression.charAt(i + 1) == '*') {
numQueue.add(Integer.parseInt(number));
number = "";
}
}
}
int i = expression.length();
// The last position in the string is yet to be operated on
// Find the second last position, if it is an operator, then the character at last position is a single digit number
if(expression.charAt(i - 2) == '-' || expression.charAt(i - 2) == '+' || expression.charAt(i - 2) == '*')
numQueue.add(Integer.parseInt(expression.substring(i - 1)));
// Else, the number might contain more than one digit
else {
number += expression.charAt(i - 1);
numQueue.add(Integer.parseInt(number));
}
}
public static int evaluateExpression() {
int number1 = numQueue.poll();
while(!opQueue.isEmpty()) {
int number2 = numQueue.poll();
char operator = opQueue.poll().charAt(0);
switch(operator) {
case '+' : number1 = number1 + number2; break;
case '-' : number1 = number1 - number2; break;
case '*' : number1 = number1 * number2; break;
}
}
return number1;
}
}
It seems that the above answers are making it more complicated than it should be. To check if it is strictly from left to right, we only need to pay attention to the location of the * operators. If we have any * operator after either a + or - operator, then it is not strictly from left to right because * has the privilege. With this being said, the code would be very simple.
A sample C++ code:
class ArithmeticCheck
{
string str_to_check;
public:
ArithmeticCheck(string str): str_to_check(str){}
bool getResult()
{
unsigned long L = str_to_check.length();
int i = 0;
char operator_;
int count_operators = 0;
int count_operators_not_multiply = 0;
int operator_last_index = 0;
while (i < L)
{
if(!isdigit(str_to_check[i]))
{
operator_ = str_to_check[i];
count_operators++;
// not true if starts or ends with an operator
if(i==0 || i==L-1)
{
return false;
}
// not true if two sequential operators
if(operator_last_index == i-1)
{
return false;
}
// not true if a * found after either a + or - operation
if( (count_operators>1) && (operator_=='*') && (count_operators_not_multiply>=1))
{
return false;
}
if(operator_ != '*')
{
count_operators_not_multiply++;
}
operator_last_index = i;
}
i++;
}
return true;
}
};
int main()
{
string str = "99*8*5*48*3";
ArithmeticCheck a(str);
cout << "The result: " << a.getResult() << endl;
return 0;
}
public class Test2 {
public static void main(String[] args)
{
String a = "3*4+8-9";
int l = a.length();
int counter =0 ;
int result=0;
while(counter<l)
{
if(counter==0)
{
String a1 = Character.toString((a.charAt(counter)));
int b1 = Integer.parseInt(a1);
counter++;
char b2 = a.charAt(counter);// operator
counter++;
String a2 = Character.toString((a.charAt(counter)));
int b3 = Integer.parseInt(a2);
counter++;
if(b2=='+') result = b1+b3;
else if(b2=='*') result = b1*b3;
else if(b2=='-') result = b1-b3;
}
else{
char b2 = a.charAt(counter);// operator
counter++;
String a1 = Character.toString((a.charAt(counter)));
int b1 = Integer.parseInt(a1);
counter++;
if(b2=='+') result = result+b1;
else if(b2=='*') result = result*b1;
else if(b2=='-') result = result-b1;
}
}
System.out.println(result);
}
}
Usually with this, we'd use the shunting yard algorithm to evaluate this with order of operations- convert to RPN then use 2 stacks. Since order of ops is being ignored here, this makes our lives a lot easier.
- SK March 17, 2015Keep one stack for numbers and another for operators. Start from the end of the string, pushing numbers on top of the number stack and operators on top of the operator stack.
Now that every number is pushed on the number stack and every operator is pushed on the operator stack we begin.
With whatever operator is on top of the operator stack, pop the top number, use the operator on the popped number and the currently top of the number stack number, then place this resulting number on top of the number stack. Pop the operator from the operator stack.
Repeat this process until there is one number on the number stack and no operators on the operator stack. If this isn't the result, then the string is invalid.