Facebook Interview Question Software Engineers
Country: Israel
Interview Type: Phone Interview
Same idea, C++ implementation
vector<string> tokenize(string & s, char delimiter) {
vector<string> tokens;
int left = 0; int pos = 0;
while (left < s.size()) {
pos = s.find(delimiter, left);
if (pos == string::npos) pos = s.size();
if (pos - left != 0) {
string token = s.substr(left, pos - left);
tokens.push_back(token);
}
left = pos + 1;
}
return tokens;
}
int parse_expression(string & s) {
if (s.size() == 0) return ERROR_VALUE;
vector<string> summands = tokenize(s, '+');
int result = 0;
for (int i = 0; i < summands.size(); ++i) {
int product = 1;
vector<string> factors = tokenize(summands[i], '*');
for (int j = 0; j < factors.size(); ++j) {
product *= stoi(factors[j]);
}
result += product;
}
return result;
}
Same idea, using more functional approach.
int ans =
Arrays.asList(input.split("\\+"))
.stream()
.map(x -> Arrays.asList(x.split("\\*"))
.stream()
.mapToInt(Integer::parseInt)
.reduce((a, b) -> a * b))
.mapToInt(x -> x.getAsInt())
.reduce((a, b) -> (a + b)).getAsInt();
Same idea, using more functional approach.
int ans =
Arrays.asList(input.split("\\+"))
.stream()
.map(x -> Arrays.asList(x.split("\\*"))
.stream()
.mapToInt(Integer::parseInt)
.reduce((a, b) -> a * b))
.mapToInt(x -> x.getAsInt())
.reduce((a, b) -> (a + b)).getAsInt();
Same idea, using more functional approach.
int ans =
Arrays.asList(input.split("\\+"))
.stream()
.map(x -> Arrays.asList(x.split("\\*"))
.stream()
.mapToInt(Integer::parseInt)
.reduce((a, b) -> a * b))
.mapToInt(x -> x.getAsInt())
.reduce((a, b) -> (a + b)).getAsInt();
Do not overcomplicate it - all you have to do is addition and multiplication.
#include <iostream>
#include <stack>
#include <string>
bool
is_digit(char c) {
return (c >= '0' and c <= '9');
}
int
get_number(const std::string& s, int& pos) {
int num = 0;
while (pos < s.length() and is_digit(s[pos])) {
num *= 10;
num += (s[pos] - '0');
pos++;
}
return num;
}
int
eval(const std::string& s) {
int pos = 0;
int cur_sum = 0;
int cur_prod = 1;
while (pos < s.length()) {
int n = get_number(s, pos);
if (pos < s.length() and s[pos] == '*' ) {
cur_prod *= n;
pos++;
} else {
cur_sum += cur_prod * n;
cur_prod = 1;
pos++;
}
}
return cur_sum;
}
int
main(int argc, char* argv[]) {
if (argc > 1) {
std::cout << eval(argv[1]) << std::endl;
}
return 0;
}
Your code assumes that there is no more than one consecutive multiplication.
Trace it for:
2 * 3 * 4 * 5 * 6 + 7 + 8 + 9
No, it does not. Note that cur_prod is not reset on '*' - the product of all multiplied numbers is accumulated in cur_prod. It returns 744 for 2*3*4*5*6+7+8+9.
i think this code fails if theres no addition at all e.g. 3*5 as cur_sum is never updated
.Parse the input string
.If input == 'a number' then push input to a stack
.If input == '+' ignore and continue
.if input == '*' then pop the top of stack(tos) then multiply with the next number and push it back to the stack.
.Once the end of string is reached then pop the tos and add until the stack is empty.
Same here. Code in python (parsing could have been done with regular expression instead of this mess)
#interpret string of + and * expression
from collections import deque
def interpret(s):
stack = []
tokens = tokenize(s)
for t in tokens:
stack.append(t)
if stack[len(stack)-2] == '*':
mul_result = stack[len(stack)-1] * stack[len(stack)-3]
stack = stack[:-3] #pop
stack.append(mul_result)
sum = 0
for n in stack:
if n != '+':
sum += n
return sum
def parse_leading_number(s):
number = ''
for i in range(len(s)):
number += (s[i])
if i < len(s)-1 and s[i+1] in '+*':
break
number = int(number)
return number, i #i is pos of the last char
def tokenize(s):
ret = []
if not s:
return []
if s[0] in '+*':
return [s[0]] + tokenize(s[1:])
number, i = parse_leading_number(s)
return [number] + tokenize(s[i+1:])
#test
print interpret('1+2*4')
Evaluating without precedence is straight forward.
With Precedence:
Can make use of the following approaches:
1.Recursive-descent recognition
2.The shunting yard algorithm
3.The classic solution
4.Precedence climbing
The Shunting Yard Algo Approach:
The idea of the shunting yard algorithm is to keep operators on a stack until both their operands have been parsed. The operands are kept on a second stack.
The key to the algorithm is to keep the operators on the operator stack ordered by precedence (lowest at bottom and highest at top), at least in the absence of parentheses. Before pushing an operator onto the operator stack, all higher precedence operators are cleared from the stack.
Ex:
To evaluate 3 + 4 * 2 + 8.
Intuitively, you "know" you have to do the 4 * 2 first, but how do you get this result?
The key is to realize that when you're scanning the string from left to right, you will evaluate an operator when the operator that follows it has a lower (or equal to) precedence.
In the context of the example, here's what you want to do:
Look at: 3 + 4, don't do anything.
Now look at 3 + 4 * 2, still don't do anything.
Now look at 3 + 4 * 2 + 8, now you know that 4 * 2 has to to be evaluated because the next operator has lower precedence.
Implementation:
> Have two stacks, one for numbers, and another for operators.
> You push numbers onto the stack all the time.
> You compare each new operator with the one at the top of the stack, if the one on top of the stack has higher priority, you pop it off the operator stack, pop the operands off the number stack, apply the operator and push the result onto the number stack.
> Now you repeat the comparison with the top of stack operator.
The stack solution is essential only if you have parentheses and more complex operators.
I think you should take advantage of being limited to + and *. I believe it can be done in a sequential scan of the string without the need for a stack.
@eng.ahmed.moustafa: In my opinion, you should take advantage of the fact that an implementation using stacks can later easily have other operators and parentheses added with little/none of the original code changed. Short code isn't always the solution as upgrade-ability/modularity is a big factor and can land you some nice bonus points in an interview if you describe it well. Unless the interviewer specifically rules out the use of data structures, I'd say a stack implementation is probably best here.
EDIT: It's almost certain that after you finished writing your code, they will ask "Ok, now what if we want to add '/' and '-' functionality, what will you do?" so making your code as modifiable and scalable is always a plus.
Since the question says the expressions have only + and * and numbers, we can leverage the fact that * precedes + and therefore can be computed as a unit. This is a fairly open question and the candidate must ask a few questions to the interviewer to make sure that he gets the proper problem.
For instance, 23+3*789 can happen? Or only single digits numbers will be sent? What about parenthesis?
To show a simplified algorithm, I will assume single digits and no parenthesis. With those assumptions, we can just have 2 loops each handling one level of precedence. The inner loop calculates the multiplication and "outputs" a number to be added by the outer loop.
PS: To handle multiple digits numbers, we just need to better tokenize the input, but the same algorithm would suffice. To handle parenthesis, then a stack or a DP solution should be used.
result, acc, i = 0, 0, 0
while i < len(input):
if (input[i] == '+'):
result = result + acc
acc = 0
elif (input[i] == '*'):
while (input[i] == '*'):
i += 1
acc = acc * int(input[i])
i += 1
result = result + acc
acc = 0
else:
acc = int(input[i])
i = i + 1
result = result + acc
print result
The question is a bit vague. Are you asking for the evaluation of the expression in a string?
One approach would be to get character array of the string and then use stack data structure to evaluate the expression.
To evaluate the expression, you also need precedence and associativity rules of the operators.
int equationparse(string s){
if(s.empty()) return INT_MIN;
int res = 0;
stack<int> operands;
stack<char> operators;
int start=0;
for(int i=0;i<s.size();i++){
switch(s[i]){
case '+':
if(start==i) return INT_MIN;
operands.push(stoi(s.substr(start, i-start)));
operators.push('+');
start = i + 1;
break;
case '*':
if(start==i) return INT_MIN;
int num = stoi(s.substr(start, i-start));
if(operands.size()>=1 && operator.top()=='*'){
num *= operands.top();
operands.pop();
operands.push(multiply);
operators.pop();
}
operands.push(num);
operators.push('*');
start = i + 1;
break;
default:break;
}
}
if(start == s.size()) return INT_MIN;
operands.push(stoi(s.substr(start)));
res = operands.top();
operands.pop();
while(!operators.empty() && !operands.empty()){
if(operators.top()=='*')
res *= operands.top();
else
res *= operands.top();
operands.pop();
operators.pop();
}
return res;
}
function tot = SolveStr(str)
% This is written in Matlab
% example:
% str = '3*5+8'
% tot = 23
% constraint: str contains numbers, '+', and '*'
% more complicated example
% str = '2+4*8+2+1*3'
% first, find the symbols
PM = find(str == '+' || str == '*'); % PM means 'plus', 'multiply'
% grab the numbers between symbols
numstr = str(findPM) = ' '; % replace symbols with blank 1-character strings
nums = num2str(numstr);
% multiply first, then add remaining terms
% assume that length(PM) = length(nums-1), that is, no dangling symbols
for i = 1:length(PM)
if str(PM(i) == '*')
% by re-writing nums, we don't have to worry about consecutive '*' symbols
if i > 1 & i < length(PM)-1
nums = [nums(1:i-1) nums(i)*nums(i+1) nums(i+2:end)];
elseif i > 1
nums = [nums(1:i-1) nums(i)*nums(i+1)];
elseif i < length(PM)-1
nums = [nums(i)*nums(i+1) nums(i+2:end)];
else
nums = nums(i)*nums(i+1);
end
end
end
tot = sum(nums);
below solution will work given each number in string is represented by single digit.
public class StringEquate {
public static void main(final String[] args) throws Exception {
final Stack<Integer> stack = new Stack<>();
final String str = "3*5+5*9+2*0";
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '*') {
stack.push(stack.pop() * Character.digit(str.charAt(++i), 10));
} else if (str.charAt(i) == '+') {
continue;
} else {
stack.push(Character.digit(str.charAt(i), 10));
}
}
int sum = 0;
while (!stack.isEmpty()) {
sum += stack.pop();
}
System.out.println(sum);
}
}
public class StringEquate {
public static void main(final String[] args) throws Exception {
final Stack<Integer> stack = new Stack<>();
final String str = "3*5+5*9+2*0";
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '*') {
stack.push(stack.pop() * Character.digit(str.charAt(++i), 10));
} else if (str.charAt(i) == '+') {
continue;
} else {
stack.push(Character.digit(str.charAt(i), 10));
}
}
int sum = 0;
while (!stack.isEmpty()) {
sum += stack.pop();
}
System.out.println(sum);
}
}
import java.util.*;
public class a {
private String input = "3+2*2+5+2*9+3";
private static Stack <Integer> stack = new Stack <Integer> ();
public static void main (String[] args) {
a a1 = new a();
StringTokenizer st = new StringTokenizer(a1.input, "+//*", true);
String token;
while (st.hasMoreTokens()){
token = st.nextToken();
if (token.equals("+")){
} else if (token.equals("*")){
int prevVal = a1.getVal(false);
int newVal = prevVal * Integer.parseInt(st.nextToken());
stack.push(new Integer(newVal));
} else {
stack.push(new Integer(token));
}
}
System.out.println(a1.input);
System.out.println(a1.getVal(true));
}
private int getVal (boolean total){
int returnVal = 0;
try {
if (!total)
returnVal = ((Integer)stack.pop()).intValue();
else{
Iterator<Integer> iter = stack.iterator();
while (iter.hasNext()) {
int stackVal = iter.next();
returnVal += stackVal;
}
}
return returnVal;
} catch (EmptyStackException e) {return 0;}
}
}
import java.util.*;
public class a {
private String input = "3+2*2+5+2*9+3";
private static Stack <Integer> stack = new Stack <Integer> ();
public static void main (String[] args) {
a a1 = new a();
StringTokenizer st = new StringTokenizer(a1.input, "+//*", true);
String token;
while (st.hasMoreTokens()){
token = st.nextToken();
if (token.equals("+")){
} else if (token.equals("*")){
int prevVal = a1.getVal(false);
int newVal = prevVal * Integer.parseInt(st.nextToken());
stack.push(new Integer(newVal));
} else {
stack.push(new Integer(token));
}
}
System.out.println(a1.input);
System.out.println(a1.getVal(true));
}
private int getVal (boolean total){
int returnVal = 0;
try {
if (!total)
returnVal = ((Integer)stack.pop()).intValue();
else{
Iterator<Integer> iter = stack.iterator();
while (iter.hasNext()) {
int stackVal = iter.next();
returnVal += stackVal;
}
}
return returnVal;
} catch (EmptyStackException e) {return 0;}
}
}
import java.util.*;
public class a {
private String input = "3+2*2+5+2*9+3";
private static Stack <Integer> stack = new Stack <Integer> ();
public static void main (String[] args) {
a a1 = new a();
StringTokenizer st = new StringTokenizer(a1.input, "+//*", true);
String token;
while (st.hasMoreTokens()){
token = st.nextToken();
if (token.equals("+")){
} else if (token.equals("*")){
int prevVal = a1.getVal(false);
int newVal = prevVal * Integer.parseInt(st.nextToken());
stack.push(new Integer(newVal));
} else {
stack.push(new Integer(token));
}
}
System.out.println(a1.input);
System.out.println(a1.getVal(true));
}
private int getVal (boolean total){
int returnVal = 0;
try {
if (!total)
returnVal = ((Integer)stack.pop()).intValue();
else{
Iterator<Integer> iter = stack.iterator();
while (iter.hasNext()) {
int stackVal = iter.next();
returnVal += stackVal;
}
}
return returnVal;
} catch (EmptyStackException e) {return 0;}
}
}
I felt that this problem ate me alive. I need to practice more.
For this solution I used multiplication having precedence over sum so I've used a stack to hold the values of for multiplication so when there is a summation I resolve all the multiplications.
void Main()
{
Console.WriteLine(Evaluate("3*5+8"));
}
public static int Evaluate(string S)
{
Stack<int> values = new Stack<int>();
int total = 0;
int prev = 0;
for(int i = 0; i < S.Length; i++)
{
if('+' == S[i])
{
while(values.Count != 0)
{
prev*= values.Pop();
}
total += prev;
prev = 0;
}
else if('*' == S[i])
{
values.Push(prev);
prev = 0;
}
else
{
prev *= 10;
prev += S[i] - '0';
}
}
while(values.Count != 0)
{
prev*= values.Pop();
}
total += prev;
return total;
}
public class TestApp {
public static void main(String[] args) {
test("3*5+8", 23);
test("0", 0);
test("1", 1);
test("2+2", 4);
test("2*2", 4);
test("2+3", 5);
test("2*3", 6);
test("3*4+2", 14);
test("2+3*4", 14);
testException("", "Expected number, found EOL");
testException("1+", "Expected number, found EOL");
testException("1*", "Expected number, found EOL");
testException("1*+2", "Expected number, found '+'");
testException("1+*2", "Expected number, found '*'");
testException("4-1", "Expected operation, found '-'");
testException("4a1", "Expected operation, found 'a'");
testException("a", "Expected number, found 'a'");
}
private static void test(String expr, int expected) {
try {
int actual = Utils.calculate(expr);
if (actual != expected) {
System.out.println("Expected: " + expected + ", actual: " + actual + ", expression: " + expr);
}
} catch (Exception e) {
System.out.println("Exception: " + e.getMessage());
}
}
private static void testException(String expr, String exceptionMessage) {
try {
Utils.calculate(expr);
System.out.print("Expected to fail: " + expr);
} catch (Exception e) {
if (!exceptionMessage.equals(e.getMessage())) {
System.out.println("Expected message: " + exceptionMessage + ", actual: " + e.getMessage() + ", expression: " + expr);
}
}
}
}
class Utils {
public static int calculate(String expr) {
return new Calculation(expr).calculate();
}
private static class Calculation {
final String expr;
int index = 0;
Calculation(String expr) {
this.expr = expr;
}
public int calculate() {
int result = 0;
int pending = readNumber();
while (index < expr.length()) {
char ch = expr.charAt(index++);
if (ch == '*') {
pending *= readNumber();
} else if (ch == '+') {
result += pending;
pending = readNumber();
} else {
throw new RuntimeException("Expected operation, found '" + ch + "'");
}
}
return result + pending;
}
int readNumber() {
if (index >= expr.length()) {
throw new RuntimeException("Expected number, found EOL");
}
char ch = expr.charAt(index);
if (!isNumber(ch)) {
throw new RuntimeException("Expected number, found '" + ch + "'");
}
int number = toDigit(ch);
index++;
while (index < expr.length()) {
ch = expr.charAt(index);
if (isNumber(ch)) {
number = 10 * number + toDigit(ch);
index++;
} else {
break;
}
}
return number;
}
boolean isNumber(char ch) {
return ch >= '0' && ch <= '9';
}
int toDigit(char ch) {
return ch - '0';
}
}
}
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 main (String[] args) throws java.lang.Exception
{
// your code goes here
System.out.println(getResult("3*5+8*2+1"));
}
public static int getResult(String equation)
{
Deque<Integer> numStack = new ArrayDeque<Integer>();
Deque<Character> opStack = new ArrayDeque<Character>();
int len = equation.length();
String num = "";
for (int i = 0; i<len; i++)
{
if(equation.charAt(i) == '+')
{
numStack.push(Integer.parseInt(num));
num = "";
if(opStack.isEmpty())
opStack.push('+');
else
{
while(!opStack.isEmpty())
{
int value = opStack.pop()=='*'? numStack.pop()*numStack.pop():numStack.pop()+numStack.pop();
numStack.push(value);
}
opStack.push('+');
}
}
else if(equation.charAt(i) == '*')
{
numStack.push(Integer.parseInt(num));
num = "";
if(opStack.isEmpty() || opStack.peek()=='+')
opStack.push('*');
else if(opStack.peek()=='*')
{
while(opStack.peek()=='*')
{
int value = numStack.pop()*numStack.pop();
numStack.push(value);
opStack.pop();
}
opStack.push('*');
}
}
else
{
num = num+equation.charAt(i);
if(i==len-1)
{
numStack.push(Integer.parseInt(num));
while(!opStack.isEmpty())
{
int value = opStack.pop()=='*'? numStack.pop()*numStack.pop():numStack.pop()+numStack.pop();
numStack.push(value);
}
}
}
}
return numStack.pop();
}
}
Solution without using stack and library methods -
public static void evaluate() {
String str = "2+13+4*5*2+4*3+6";
int addresult = 0;
int multiplyresult = 1;
char prevop = '+';
for(int i=0; i<str.length(); i++) {
char ch = str.charAt(i);
int conv = ch - '0';
boolean isDigit = (conv >= 0 && conv <= 9);
int n = 0;
while (isDigit) {
n = n*10+conv;
i++;
if(i < str.length()) {
ch = str.charAt(i);
conv = ch - '0';
isDigit = (conv >= 0 && conv <= 9);
} else {
isDigit = false;
}
}
if(i == str.length()) {
if(prevop == '*') {
addresult += multiplyresult*n;
} else {
addresult+=n;
}
}
else if(ch == '+' && prevop == '+') {
addresult+=n;
prevop = ch;
} else if(ch == '*' && prevop == '+') {
multiplyresult *= n;
prevop = ch;
} else if(ch == '*' && prevop == '*') {
multiplyresult*=n;
prevop = ch;
} else if(ch == '+' && prevop == '*') {
multiplyresult*=n;
addresult =multiplyresult+addresult;
multiplyresult = 1;
prevop = ch;
}
}
System.out.println(addresult);
}
In C++, supporting numbers > 9.
#include <string>
#include <iostream>
#include <sstream>
#include <stack>
std::string IntToString(int nValue)
{
std::string result;
std::ostringstream convert;
convert << nValue;
result = convert.str();
return result;
}
int StringToInt(std::string str)
{
int nResult;
if (!(std::istringstream(str) >> nResult))
nResult = 0;
return nResult;
}
int Calculate(const std::string& formula)
{
std::stack<std::string> stack;
for (int i = 0; i < formula.length(); i++)
{
// We add a number
if (formula[i] != '*'
&& formula[i] != '+')
{
std::string number;
while (i < formula.length()
&& formula[i] != '+'
&& formula[i] != '*')
{
number = number + formula[i];
i++;
}
i--;
// Check if prev operation is multiply
if (!stack.empty() && stack.top() == "*")
{
stack.pop();
int nb1 = StringToInt(stack.top());
stack.pop();
int result = nb1 * StringToInt(number);
stack.push(IntToString(result));
}
else
stack.push(number);
}
else if (formula[i] == '*')
{
std::string operand(1, formula[i]);
stack.push(operand);
}
}
// Just add all remaining numbers on the stack together
int result = 0;
while (!stack.empty())
{
result += StringToInt(stack.top());
stack.pop();
}
return result;
}
int main(int argc, const char * argv[]) {
/* Calculation */
std::string formula = "555+8*2";
std::cout << Calculate(formula) << std::endl;
}
public static int Evaluate(string S)
{
int number = 0;
var numbers = new Stack<int>();
var operations = new Stack<char>();
for(int i = 0; i < S.Length; i++)
{
char s = S[i];
if(char.IsDigit(s))
{
number *= 10;
number += s - '0';
}
else
{
numbers.Push(number);
number = 0;
if(s == '*')
{
operations.Push('*');
}
else if(s == '+')
{
operations.Push('+');
}
}
}
numbers.Push(number);
int temp = 0;
while(operations.Count > 0)
{
Console.WriteLine(numbers);
if(operations.Peek() == '*')
{
int p1 = numbers.Pop();
int p2 = numbers.Pop();
numbers.Push(p1*p2);
operations.Pop();
}
else if(operations.Peek() == '+')
{
operations.Pop();
if(operations.Count > 0 && operations.Peek() == '*')
{
temp = numbers.Pop();
}
else
{
int p1 = numbers.Pop() + temp;
int p2 = numbers.Pop();
numbers.Push(p1 + p2);
temp = 0;
}
}
}
return numbers.Pop() + temp;
}
public boolean isSum(char c){
if(c=='+') return true;
return false;
}
public boolean isMultiply(char c){
if(c=='*') return true;
return false;
}
/* 3*5+10 */
public int equation(String input){
Stack<Integer> theStack = new Stack<Integer>();
int num1 = 0;
int num2 = 0;
if(!Character.isDigit(input.charAt(0))){
return -1;
}
for(int i=0; i<input.length(); i++){
if(Character.isDigit(input.charAt(i))){
theStack.push(Character.getNumericValue(input.charAt(i)));
}
else if(isMultiply(input.charAt(i))){
i++;
if(Character.isDigit(input.charAt(i)) && i< input.length()){
num2 = Character.getNumericValue(input.charAt(i));
num1 = theStack.pop();
int res = num1 * num2;
theStack.push(res);
//i++;
}
else{
return -1;
}
}
else if(isSum(input.charAt(i))){
i++;
if(Character.isDigit(input.charAt(i)) && i< input.length()){
num2 = Character.getNumericValue(input.charAt(i));
num1 = theStack.pop();
int res = num1 + num2;
theStack.push(res);
//i++;
}
else{
return -1;
}
}
}
return theStack.pop();
}
My proposal in Java:
{
public static void main(String[] args) throws FileNotFoundException {
System.out.println(printExpression("2*3*5+8+2+3"));
}
private static int printExpression(String input) {
Deque<Integer> digits = new ArrayDeque<Integer>();
Deque<Character> operators = new ArrayDeque<Character>();
for(int i = 0; i < input.length(); i++){
if(input.charAt(i) != '*' && input.charAt(i) != '+')
digits.addLast(input.charAt(i) - '0');
else if(input.charAt(i) == '*')
operators.addLast('*');
else
operators.addLast('+');
}
int operator_size = operators.size();
for(int i = 0; i < operator_size; i++){
if(operators.getFirst() == '*'){
int a = digits.getFirst();
digits.removeFirst();
int b = digits.getFirst();
digits.removeFirst();
operators.removeFirst();
digits.addFirst(a * b);
} else {
operators.removeFirst();
digits.addLast(digits.getFirst());
digits.removeFirst();
}
}
int sum = 0;
while(!digits.isEmpty()){
sum += digits.getFirst();
digits.removeFirst();
}
return sum;
}
}
Worked in java..
private void parse(String expression) {
expression = expression.replace(" ", "");
String[] expressionSplitOnAdd = expression.split("\\+");
String expressionOutput = "0";
for(String value : expressionSplitOnAdd){
String temValue = "";
if(value.contains("*")){
String[] expressionSplitOnMul = value.split("\\*");
String multipliedValue = "1";
for(String mulValue : expressionSplitOnMul){
multipliedValue = "" + Integer.valueOf(multipliedValue) * Integer.valueOf(mulValue);
}
temValue = multipliedValue;
}else{
temValue = value;
}
expressionOutput = "" + (Integer.valueOf(expressionOutput) + Integer.valueOf(temValue));
}
System.out.println(expressionOutput);
}
public long evaluateExpression(String input) {
//Split string using '+' delimeter
String multiplies[] = input.split("+");
long answer = 0l;
//add those expressions
for (int i=0; i<multiplies.length; i++) {
answer += evaluateMultiplies(multiplies[i]);
}
return answer;
}
// evaluates multiply operator
private long evaluateMultiplies(String input) {
long answer = 1l;
String numbers[] = input.split("*");
for (int i=0; i<numbers.length; i++) {
answer *= Long.parseLong(numbers[i]);
}
return answer;
}
public long evaluateExpression(String input) {
//Split string using '+' delimeter
String multiplies[] = input.split("+");
long answer = 0l;
//add those expressions
for (int i=0; i<multiplies.length; i++) {
answer += evaluateMultiplies(multiplies[i]);
}
return answer;
}
// evaluates multiply operator
private long evaluateMultiplies(String input) {
long answer = 1l;
String numbers[] = input.split("*");
for (int i=0; i<numbers.length; i++) {
answer *= Long.parseLong(numbers[i]);
}
return answer;
}
public long evaluateExpression(String input) {
//Split string using '+' delimeter
String multiplies[] = input.split("+");
long answer = 0l;
//add those expressions
for (int i=0; i<multiplies.length; i++) {
answer += evaluateMultiplies(multiplies[i]);
}
return answer;
}
// evaluates multiply operator
private long evaluateMultiplies(String input) {
long answer = 1l;
String numbers[] = input.split("*");
for (int i=0; i<numbers.length; i++) {
answer *= Long.parseLong(numbers[i]);
}
return answer;
}
i think approach of the stack is a better option, also making assumption that b/w 2 operator there is a single digit is important. I tried first without stack approach,it passed for some of the value but failed for the edges. Here is my code which works fine when the input is Str="3*5+8" or " 3+5*8" or "3+5*8+2" but failed when the same operator is consecutive like "3+5*8*2"
public class SecondProgram {
public static void main(String [] args) {
String str="3+8*5+2";
int result =0,a=0;
for(int i=0;i<str.length();i++){
if(str.charAt(i) == '*') {
if(result ==0 ) {
result= ((int)(str.charAt(i-1))-48) *((int)(str.charAt(i+1))-48);
result+=a;
//a=0;
}
else {
result=result * ((int)(str.charAt(i+1))-48);
}
}
else if (str.charAt(i)== '+'){
if ( result ==0) {
a= (int)(str.charAt(i-1))-48;
}
else {
result = result +((int)(str.charAt(i+1))-48);
}
}
else {
continue;
}
}
System.out.println("The result is "+result);
}
}
// Note: this code fails when we have same operator consecutive to each other, i think approach of stack is the better ootion
//to avoid edge cases
public class SecondProgram {
public static void main(String [] args) {
String str="3+8*5+2";
int result =0,a=0;
for(int i=0;i<str.length();i++){
if(str.charAt(i) == '*') {
if(result ==0 ) {
result= ((int)(str.charAt(i-1))-48) *((int)(str.charAt(i+1))-48);
result+=a;
//a=0;
}
else {
result=result * ((int)(str.charAt(i+1))-48);
}
}
else if (str.charAt(i)== '+'){
if ( result ==0) {
a= (int)(str.charAt(i-1))-48;
}
else {
result = result +((int)(str.charAt(i+1))-48);
}
}
else {
continue;
}
}
System.out.println("The result is "+result);
}
}
String input = "10*2*3+5+5+2*10";
StringTokenizer st = new StringTokenizer(input, "+//*", true);
while (st.hasMoreTokens()) {
String token = st.nextToken();
if(token.equals("*")){
int val = Integer.parseInt(st.nextToken());
int prev = stack.pop();
int temp = prev * val;
stack.push(temp);
}else if(token.equals("+")){
}else{
System.out.println("push:"+ token);
stack.push(Integer.parseInt(token));
}
}
int total = 0;
while(stack.size()>0){
total += stack.pop();
}
System.out.println(total);
public class StringEquation {
public static int equation(String formula) {
if (formula == null)
return 0;
formula = formula.replaceAll(" ", "");
if (formula.isEmpty())
return 0;
int sum = 0;
String[] additions = formula.split("\\+");
for (int i = 0; i < additions.length; i++) {
int mul = 1;
String[] multiplications = additions[i].split("\\*");
for (int j = 0; j < multiplications.length; j++) {
mul *= Integer.parseInt(multiplications[j]);
}
sum += mul;
}
return sum;
}
public static void main(String[] args) {
System.out.println(equation("3*5+8"));
System.out.println(equation("3+5+8"));
}
}
I used two stacks on for numbers and the other for operators. This algorithm examine the expression from the back to front.
#include <list>
#include <string>
#include <climits>
#include <iostream>
using namespace std;
bool isNum(char c)
{
return (c >='0' && c<='9');
}
bool isOp(char c)
{
return (c =='+'|| c== '-'||c=='/'|| c=='*');
}
bool multiOrDiv(char c)
{
return (c == '*' || c == '/');
}
int compute(int l, int r, char op)
{
if (op =='+')
return l+r;
else if (op == '-')
return l-r;
else if (op == '*')
return l*r;
else if (op == '/')
return l/r;
return INT_MIN;
}
int eval_expr(string input)
{
list<int> numbers;
list<char> ops;
string token;
int result;
for (int i = input.length()-1; i >= 0; i--)
{
int num;
if (isNum(input[i]))
{
token.insert(0,1, input[i]);
if (i == 0 && token.length())
{
num = atoi(token.c_str());
numbers.push_back(num);
}
} else if (isOp(input[i]))
{
if (token.length())
{
num = atoi(token.c_str());
numbers.push_back(num);
token = "";
}
if (!multiOrDiv(input[i]))
{
char op = ops.back();
while (multiOrDiv(op) && numbers.size() >1)
{
ops.pop_back();
int l = numbers.back();
numbers.pop_back();
int r = numbers.back();
numbers.pop_back();
int result = compute(l, r, op);
numbers.push_back(result);
op = ops.back();
}
}
ops.push_back(input[i]);
}
}
while (numbers.size() >1 && ops.size() >0)
{
char op = ops.back();
ops.pop_back();
int l = numbers.back();
numbers.pop_back();
int r = numbers.back();
numbers.pop_back();
result = compute(l, r, op);
numbers.push_back(result);
}
return numbers.back();
}
This is C++ solution:
#include <list>
#include <string>
#include <climits>
#include <iostream>
using namespace std;
bool isNum(char c)
{
return (c >='0' && c<='9');
}
bool isOp(char c)
{
return (c =='+'|| c== '-'||c=='/'|| c=='*');
}
bool multiOrDiv(char c)
{
return (c == '*' || c == '/');
}
int compute(int l, int r, char op)
{
if (op =='+')
return l+r;
else if (op == '-')
return l-r;
else if (op == '*')
return l*r;
else if (op == '/')
return l/r;
return INT_MIN;
}
int eval_expr(string input)
{
list<int> numbers;
list<char> ops;
string token;
int result;
for (int i = input.length()-1; i >= 0; i--)
{
int num;
if (isNum(input[i]))
{
token.insert(0,1, input[i]);
if (i == 0 && token.length())
{
num = atoi(token.c_str());
numbers.push_back(num);
}
} else if (isOp(input[i]))
{
if (token.length())
{
num = atoi(token.c_str());
numbers.push_back(num);
token = "";
}
if (!multiOrDiv(input[i]))
{
char op = ops.back();
while (multiOrDiv(op) && numbers.size() >1)
{
ops.pop_back();
int l = numbers.back();
numbers.pop_back();
int r = numbers.back();
numbers.pop_back();
int result = compute(l, r, op);
numbers.push_back(result);
op = ops.back();
}
}
ops.push_back(input[i]);
}
}
while (numbers.size() >1 && ops.size() >0)
{
char op = ops.back();
ops.pop_back();
int l = numbers.back();
numbers.pop_back();
int r = numbers.back();
numbers.pop_back();
result = compute(l, r, op);
numbers.push_back(result);
}
return numbers.back();
}
Simple recursive-descent expression parser, written in C#
// Given a string containing a valid arithmetic expression, evaluate the expression.
// String does not contain any whitespace, numbers are positive integers,
// and the allowed operators are + - * /
using System;
class Program
{
static int ScanNumber(string s, ref int i)
{
int start = i;
for (; i < s.Length && Char.IsDigit(s[i]); i++)
;
return int.Parse(s.Substring(start, i - start));
}
static int ParseProduct(string s, ref int i)
{
int result = ScanNumber(s, ref i);
while (i < s.Length)
{
char op = s[i];
if (op != '*' && op != '/')
break;
i++;
int n = ScanNumber(s, ref i);
if (op == '*')
result *= n;
else
result /= n;
}
return result;
}
static int ParseSum(string s)
{
int i = 0;
int sum = ParseProduct(s, ref i);
while (i < s.Length)
{
char op = s[i];
i++;
int n = ParseProduct(s, ref i);
if (op == '+')
sum += n;
else
sum -= n;
}
return sum;
}
static void Main(string[] args)
{
for (; ; )
{
string s = Console.ReadLine();
if (s.Length == 0)
break;
int result = ParseSum(s);
Console.WriteLine(result);
}
}
}
// Given a string containing a valid arithmetic expression, evaluate the expression.
// String does not contain any whitespace, numbers are positive integers,
// and the allowed operators are + - * /
using System;
class Program
{
static int ScanNumber(string s, ref int i)
{
int start = i;
for (; i < s.Length && Char.IsDigit(s[i]); i++)
;
return int.Parse(s.Substring(start, i - start));
}
static int ParseProduct(string s, ref int i)
{
int result = ScanNumber(s, ref i);
while (i < s.Length)
{
char op = s[i];
if (op != '*' && op != '/')
break;
i++;
int n = ScanNumber(s, ref i);
if (op == '*')
result *= n;
else
result /= n;
}
return result;
}
static int ParseSum(string s)
{
int i = 0;
int sum = ParseProduct(s, ref i);
while (i < s.Length)
{
char op = s[i];
i++;
int n = ParseProduct(s, ref i);
if (op == '+')
sum += n;
else
sum -= n;
}
return sum;
}
static void Main(string[] args)
{
for (; ; )
{
string s = Console.ReadLine();
if (s.Length == 0)
break;
int result = ParseSum(s);
Console.WriteLine(result);
}
}
}
Solution in O(n) time and constant space:
public class StringMath {
public static void main(String[] args) {
System.out.println(evaluate("11+2*3+40*2+1")); //prints: 98
}
static class NumPos {
public int num;
public int pos;
public NumPos(int num, int pos) {
this.num = num;
this.pos = pos;
}
}
public static int evaluate(String s) {
final char[] exp = s.toCharArray();
int pos = 0;
int sum = 0;
while (pos < exp.length) { //add numbers until reaching end of expression
int product = 1;
do { //multiply numbers until reaching '+' or end of expression
NumPos numPos = getNextNumAndPos(exp, pos);
int num = numPos.num;
pos = numPos.pos + 1;
product *= num;
} while (pos < exp.length && exp[pos - 1] == '*');
sum += product;
}
return sum;
}
public static NumPos getNextNumAndPos(char[] exp, int start) {
int num = 0;
int i = start;
while (i < exp.length && Character.isDigit(exp[i])) {
num = num * 10 + (exp[i++] - '0');
}
return new NumPos(num, i);
}
}
Stack is the generalized way to go, but in this case something very simple would do.
The idea is to split the string by '+' operator. Now, the resultant splits are basically multiplication operations. Do them first (by spliting them on '*') and then add the results.
PseudoCode:
- Jayanta Mondal February 25, 2015int ans = 0; string[] Pluses = InputString.split('+'); for (String multString: Pluses) { String[] mults = multString.split('*'); int multAcc = 1; for (String num: mults) { multAcc *= Integer.parseInt(num); } sum += multAcc; }