This calculator takes values that could be written in a browsers route path as a single string. It then returns the result as a number (or an error message).

Route paths use the '/' symbol so this can't be in our calculator. Instead we are using the '$' symbol as our divide operator.

You will be passed a string of any length containing numbers and operators:

* '+' = add        
* '-' = subtract  
* '*' = multiply 
* '$' = divide   

Your task is to break the string down and calculate the expression using this order of operations. (division => multiplication => subtraction => addition)

If you are given an invalid input (i.e. any character except `.0123456789+-*$`) you should return the error message:`'400: Bad request'`

### Remember:

1. Operations are infinite
2. Order of operations is imperitive
3. No `eval` or equivalent functions

**Examples:**
```python
calculate('1+1')     => '2'
calculate('10$2')    => '5'
calculate('1.5*3')   => '4.5'

calculate('5+5+5+5') => '20'

calculate('1000$2.5$5+5-5+6$6') =>'81'

calculate('10-9p')   =>  '400: Bad request'
```

### Further Notes - Parameters outside of this challenge:

- Brackets e.g. 10*(1+2)
- Square root, log, % or any other operators
- Unary minus (10*-1)
- Bad mathematical input (10**$10 or 5+5$)
- You may have to deal with floats

If enjoy this and want something harder please see http://www.codewars.com/kata/evaluate-mathematical-expression/ for making a much more complicated calculator. This is a good kata leading up to that.

Difficulty: interview

Starter code:

def calculate(expression):
	

Solutions:
import re

ADDSUB, MULDIV = '+-', '*$'

def calculate(expression):
    return "400: Bad request" if re.search(r'[^+*$\d.-]', expression) else parseAndEval(expression, ADDSUB)

def parseAndEval(expression, ops):
    v = 0
    for op,part in re.findall(r'([{0}])?([^{0}]+)'.format(ops), expression):
        if not op:    v  = float(part) if ops == MULDIV else parseAndEval(part, MULDIV)
        elif op=='*': v *= float(part)
        elif op=='$': v /= float(part)
        elif op=='+': v += parseAndEval(part, MULDIV)
        elif op=='-': v -= parseAndEval(part, MULDIV)
    return v

def tokenize(expression):
    result = []
    curr = ''
    for chr in expression:
        if chr.isdigit() or chr == '.':
            curr += chr
        elif chr in '$*-+':
            result.extend([float(curr), chr])
            curr = ''
        else:
            raise ValueError('invalid input')
    if curr:
        result.append(float(curr))
    return result
    
def calculate(expression):
    ops = {
        '+': lambda x, y: x + y,
        '-': lambda x, y: x - y,
        '*': lambda x, y: x * y,
        '$': lambda x, y: x / y,
    }
    
    try:
        l = tokenize(expression)
    except ValueError:
        return '400: Bad request'
    
    for op in '$*-+':
        while op in l:
            i = l.index(op)
            l = l[:i-1] + [ops[op](l[i-1], l[i+1])] + l[i+2:]
    
    return l[0]

def calculate(s):
    if any(c not in '.0123456789+-*$' for c in s): return '400: Bad request'
    
    tokens = [float(e) if e not in '$*-+' else e for e in s.replace('+', ' + ').replace('-', ' - ').replace('*', ' * ').replace('$', ' $ ').split()]
    
    for c in '$*-+':
        r = []
        for t in tokens:
            if r and r[-1] == c:
                r.pop()
                t = {'$':lambda a,b: a/b, '*':lambda a,b: a*b, '-':lambda a,b: a-b, '+':lambda a,b: a+b}[c](r.pop(), t)
            r.append(t)
                
        tokens = r
    
    return tokens.pop()

from operator import truediv, mul, sub, add
operators = {'/':truediv,'*':mul,'+':add,'-':sub}
order = [{'/', '*'}, {'-', '+'}]
    
def calculate(expression):
    expression = expression.replace('$','/') 
    for i in '+*/-':
        expression = expression.replace(i,' '+i+' ')
    l = expression.split()
    try:
        for i in range(2):
            n = 0
            while n < len(l):
                if l[n] in order[i]:
                    l[n-1] = operators[l[n]](float(l.pop(n-1)),float(l.pop(n)))
                else:n+=1   
        return float(l[0])
    except:
        return '400: Bad request'

import re
def calculate(expression):
    if re.search(r'[^\.0123456789+\-*$]', expression): return '400: Bad request'
    if re.match('^(?:\d+\.)?\d+$', expression): return float(expression)
    return (
        (
            lambda m:
                (lambda x, o, y: ({ '+': x + y, '-': x - y, '*': x * y, '$': x / y })[o])
                (calculate(m.group(1)), m.group(2), calculate(m.group(3)))
                if m else 0
        )
        (re.search('(.+)([+-])(.+)', expression) or re.search('(.+)([*$])(.+)', expression))
    )


def calculate(s):
    try:
        s = re.sub(r'([+*\-$])', r' \1 ', s).split()
        def doall(s_):
              while s_ in s:
                  find = s.index(s_)
                  t ,t1 = float(s[find-1]),float(s.pop(find+1))
                  s[find-1] = t/t1 if s_=="$"else t*t1 if s_=="*"else t-t1 if s_== "-"else t+t1
                  s.pop(find)
        doall('$')
        doall('*')
        doall('-')
        doall('+')
        return float(s[0])
    except : return "400: Bad request"

def operation(op1, op2, op):
    if op == "*":
        return op1 * op2
    elif op == "+":
        return op1 + op2
    elif op == "-":
        return op1 - op2
    else:
        return op1 / op2

def calculate(expression):
    i, lst, num = 0, [], ""
    if "." in expression:
        if expression.replace(".", "").isdigit():
            return float(expression)
    while i < len(expression):
        if not expression[i].isdigit():
            if expression[i] in "+-*$":
                lst.append(int(num))
                lst.append(expression[i])
                num = ""
            else:
                return "400: Bad request"
        else:
            num += expression[i]
        i += 1
    if expression[i-1].isdigit():
        lst.append(int(num))
    length = len(lst)
    while(True):
        if "*" in lst and "$" in lst:
            index1, index2 = lst.index('*'), lst.index('$')
            if index1 < index2 and index1-1 > -1 and index1+1 < length and (type(lst[index1-1]) == int or type(lst[index1-1]) == float) and (type(lst[index1+1]) == int or type(lst[index1+1]) == float):
                lst[index1-1] = operation(lst.pop(index1-1), lst.pop(index1), lst[index1-1])
            elif index2-1 > -1 and index2+1 < length and (type(lst[index2-1]) == int or type(lst[index2-1]) == float) and (type(lst[index2+1]) == int or type(lst[index2+1]) == float):
                lst[index2-1] = operation(lst.pop(index2-1), lst.pop(index2), lst[index2-1])
            else:
                return "400: Bad request"
        elif "*" in lst:
            index = lst.index("*")
            if index-1 > -1 and index+1 < length and (type(lst[index-1]) == int or type(lst[index-1]) == float) and (type(lst[index+1]) == int or type(lst[index+1]) == float):
                lst[index-1] = operation(lst.pop(index-1), lst.pop(index), lst[index-1])
            else:
                return "400: Bad request"
        elif "$" in lst:
            index = lst.index("$")
            if index-1 > -1 and index+1 < length and (type(lst[index-1]) == int or type(lst[index-1]) == float) and (type(lst[index+1]) == int or type(lst[index+1]) == float):
                lst[index-1] = operation(lst.pop(index-1), lst.pop(index), lst[index-1])
            else:
                return "400: Bad request"
        elif "+" in lst and "-" in lst:
            index1, index2 = lst.index('+'), lst.index('-')
            if index1 < index2 and index1-1 > -1 and index1+1 < length and (type(lst[index1-1]) == int or type(lst[index1-1]) == float) and (type(lst[index1+1]) == int or type(lst[index1+1]) == float):
                lst[index1-1] = operation(lst.pop(index1-1), lst.pop(index1), lst[index1-1])
            elif index2-1 > -1 and index2+1 < length and (type(lst[index2-1]) == int or type(lst[index2-1]) == float) and (type(lst[index2+1]) == int or type(lst[index2+1]) == float):
                lst[index2-1] = operation(lst.pop(index2-1), lst.pop(index2), lst[index2-1])
            else:
                return "400: Bad request"
        elif "+" in lst:
            index = lst.index("+")
            if index-1 > -1 and index+1 < length and (type(lst[index-1]) == int or type(lst[index-1]) == float) and (type(lst[index+1]) == int or type(lst[index+1]) == float):
                lst[index-1] = operation(lst.pop(index-1), lst.pop(index), lst[index-1])
            else:
                return "400: Bad request"
        elif "-" in lst:
            index = lst.index("-")
            if index-1 > -1 and index+1 < length and (type(lst[index-1]) == int or type(lst[index-1]) == float) and (type(lst[index+1]) == int or type(lst[index+1]) == float):
                lst[index-1] = operation(lst.pop(index-1), lst.pop(index), lst[index-1])
            else:
                return "400: Bad request"
        else:
            break
    return lst.pop()

################################################################
ADD="+"
SUB="-"
MUL="*"
DIV="$"

OPS={
  ADD : lambda x,y: x+y,
  SUB : lambda x,y: x-y,
  MUL : lambda x,y: x*y,
  DIV : lambda x,y: x/y,
}

DIGITS="0123456789"

DECIMAL="."

eMsg="400: Bad request"

################################################################
class RouteError(ValueError):
  pass

  '''
  IT IS NOT ALLOWED TO USE DOUBLE UNDERSCORE SEQUENSE IN THIS C_O_D_E,
  SO I HAVE TO WRITE MY CLASSES WITHOUT _ _init_ _
  def _ _init_ _(self, text):
    self.text=text
  '''

################################################################
class Scaner:
  '''
  scans for tokens in input -
  arithmetic operations:    +   -   *   $
  and numbers:              1   2.  .3  4.5
  a decimal point is NOT a valid number, an exception is raised
  any other character also raises an exception
  '''

  '''
  IT IS NOT ALLOWED TO USE DOUBLE UNDERSCORE SEQUENSE IN THIS C_O_D_E,
  SO I HAVE TO WRITE MY CLASSES WITHOUT _ _init_ _
  def _ _init_ _(self, expression):
    self.exp=expression
    self.pos=0
    self.len=len(expression)
  '''

  def init(self, expression):
    self.exp=expression
    self.pos=0
    self.len=len(expression)

  def get_digits(self):
    res=""

    while self.pos<self.len:
      chr=self.exp[self.pos]
      if chr not in DIGITS: break
      res+=chr
      self.pos+=1

    return res

  def get_number(self):
    num=self.get_digits()
    if self.pos>=self.len: return num

    if self.exp[self.pos]==DECIMAL:
      self.pos+=1
      num+=DECIMAL+self.get_digits()
    if num==DECIMAL: raise RouteError("No digits in number.")
    return num

  def token(self):
    if self.pos>=self.len: return None

    chr=self.exp[self.pos]
    if chr in OPS:
      self.pos+=1
      return chr

    if chr in DIGITS or chr==DECIMAL:
      return self.get_number()

    self.pos+=1       # NOT nesessary
    raise RouteError("Illegal character in expression.")

################################################################
class Parser:
  '''
  parses tokens into reverse polish notation
  at first, all tokens are put into self.stk
  then they are rearranged and put into self.rpn
  1+2*3 -> 1 2 3 * +
  4-5+6 -> 4 5 - 6 +
  this class detects all errors in expression (except division by zero)
  so later we can evaluate rpn without error checking
  '''

  '''
  IT IS NOT ALLOWED TO USE DOUBLE UNDERSCORE SEQUENSE IN THIS C_O_D_E,
  SO I HAVE TO WRITE MY CLASSES WITHOUT _ _init_ _
  def _ _init_ _(self):
    self.stk=[]
    self.rpn=[]
  '''

  def init(self):
    self.stk=[]
    self.rpn=[]

  def pop(self):
    return self.stk.pop(0) if self.stk else None

  def token(self):
    return self.stk[0] if self.stk else None

  def generate_rpn(self):
    self.generate_subtraction()
    while self.token()==ADD:
      self.pop()
      self.generate_subtraction()
      self.generate_op(ADD)

    if self.stk:
      raise RouteError("Unexpected token "+self.token()+".")

  def generate_subtraction(self):
    self.generate_multiplication()
    while self.token()==SUB:
      self.pop()
      self.generate_multiplication()
      self.generate_op(SUB)

  def generate_multiplication(self):
    self.generate_division()
    while self.token()==MUL:
      self.pop()
      self.generate_division()
      self.generate_op(MUL)

  def generate_division(self):
    if self.token()==None:
      raise RouteError("Missing operand 1.")
    self.generate_operand()
    while self.token()==DIV:
      self.pop()
      self.generate_operand()
      self.generate_op(DIV)

  def generate_operand(self):
    if not self.stk:
      raise RouteError("Missing operand 2.")
    if self.token() in OPS:
      raise RouteError("Unexpected operator "+self.token()+".")
    tok=self.pop()
    self.rpn.append(float(tok) if DECIMAL in tok else int(tok))

  def generate_op(self, op):
    self.rpn.append(op)

################################################################
def tryint(num):
  '''
  converts numbers like 2.0 to 2 without fractional part,
  like it is given in examples
  '''
  inum=int(num)
  return inum if num==inum else num

def Evaluate(rpn):
  '''
  evaluates rpn; error checking is not needed, because the data
  is sintacticaly correct after Parser
  (i. e., we will never get something like [1 2 + -] or [5 5])
  '''
  stk=[]
  for t in rpn:
    if t in OPS:
      op0=stk.pop()
      stk[-1]=OPS[t](stk[-1], op0)
    else:
      stk.append(t)

  return tryint(stk[0])

################################################################
def calculate(expression):
  s=Scaner()
  s.init(expression)
  p=Parser()
  p.init()

  try:
    while True:
      t=s.token()
      if t: p.stk.append(t)
      else:
        p.generate_rpn()
        break

    res=Evaluate(p.rpn)

  except RouteError:
    res=eMsg
  except ZeroDivisionError:
    res=eMsg

  return res


def calculate(exp):
    import re
    s = [float(i) for i in re.findall(r'[.\d]+',exp)]
    ops = exp
    for i in range(10):
        ops = ops.replace(str(i),'')
    ops = ops.replace('.','')
    p = list(ops)
    for i in ['+', '-', '*','$']:
        ops = ops.replace(i,'') 
    if (ops!='') or (len(p)>=len(s)):
        return '400: Bad request'
    for i in range(len(p)):
        if p[i]=='$':
            o = i
            j = i+1
            while True:
                if s[j]=='o':
                    j = j +1
                else:
                    break
            while True:
                if s[o]=='o':
                    o = o - 1
                else:
                    break
            s[o] = s[o]/s[j]
            s[j] = 'o'
    for i in range(len(p)):
        if p[i]=='*':
            o = i
            j = i+1
            while True:
                if s[j]=='o':
                    j = j +1
                else:
                    break
            while True:
                if s[o]=='o':
                    o = o - 1
                else:
                    break
            s[o] = s[o]*s[j]
            s[j] = 'o'
    for i in range(len(p)):
        if p[i]=='-':
            o = i
            j = i+1
            while True:
                if s[j]=='o':
                    j = j +1
                else:
                    break
            while True:
                if s[o]=='o':
                    o = o - 1
                else:
                    break
            s[o] = s[o]-s[j]
            s[j] = 'o'
    for i in range(len(p)):
        if p[i]=='+':
            o = i
            j = i+1
            while True:
                if s[j]=='o':
                    j = j +1
                else:
                    break
            while True:
                if s[o]=='o':
                    o = o - 1
                else:
                    break
            s[o] = s[o]+s[j]
            s[j] = 'o'
    for i in s:
        if i != 'o':
            return i

def calculate(expression):
    print(expression)
    expression = "".join([" {} ".format(num) if num in "+-*$" else num for num in expression]).split()
    while '$' in expression:
        try:
            for num in expression:
                if num == '$':
                    first = expression.pop(expression.index(num)-1)
                    second = expression.pop(expression.index(num)+1)
                    ans = str(float(float(first)/float(second)))
                    expression[expression.index(num)] = ans
        except ValueError:
            return '400: Bad request'
    while '*' in expression:
        try:
            for num in expression:
                if num == '*':
                    first = expression.pop(expression.index(num)-1)
                    second = expression.pop(expression.index(num)+1)
                    ans = str(float(float(first)*float(second)))
                    expression[expression.index(num)] = ans
        except ValueError:
            return '400: Bad request'
    while '-' in expression:
        try:
            for num in expression:
                if num == '-':
                    first = expression.pop(expression.index(num)-1)
                    second = expression.pop(expression.index(num)+1)
                    ans = str(float(float(first)-float(second)))
                    expression[expression.index(num)] = ans
        except ValueError:
            return '400: Bad request'
    while '+' in expression:
        try:
            for num in expression:
                if num == '+':
                    first = expression.pop(expression.index(num)-1)
                    second = expression.pop(expression.index(num)+1)
                    ans = str(float(float(first)+float(second)))
                    expression[expression.index(num)] = ans
        except ValueError:
            return '400: Bad request'
    try:
        return float(expression[0])
    except ValueError:
        return '400: Bad request'