Given a string s which represent an expression, evaluate this expression.
Integer division should truncate towards zero.
 
Example 1:
Input: s = "10*20+10"
Output: 210
Example 2:
Input: s = "16*5-5/15"
Output: 80
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function calculate() which takes s as input parameter and returns the value of the expression.
 
Expected Time Compelxity: O(|s|)
Expected Space Complexity: O(1)
 
Constraints:
1 <= |s| <= 10^{5}
^{s is a valid expression.}
Note: The answer is guaranteed to fit in a 32-bit integer.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

	def calculate(self, s):

		#Code here



Solutions:
class Solution:

	def __init__(self):
		self.priority = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}

	def isoperator(self, ch):
		return ch in self.priority

	def infix_postfix(self, s):
		n = len(s)
		exp = ''
		stack = []
		i = 0
		while i < n:
			temp = ''
			while i < n and s[i].isnumeric():
				temp += s[i]
				i += 1
			exp += temp + '_'
			while i < n and len(stack) != 0 and (self.priority[stack[-1]] >= self.priority[s[i]]):
				exp += stack.pop()
			if i < n:
				stack.append(s[i])
			i += 1
		while len(stack) != 0:
			exp += stack.pop()
		return exp

	def calculation(self, s):
		n = len(s)
		stack = []
		i = 0
		while i < n:
			temp = ''
			while i < n and s[i].isnumeric():
				temp += s[i]
				i += 1
			if i < n and len(stack) > 1 and self.isoperator(s[i]):
				a = stack.pop()
				b = stack.pop()
				if s[i] == '+':
					res = a + b
				if s[i] == '-':
					res = b - a
				if s[i] == '*':
					res = a * b
				if s[i] == '/':
					res = b // a
				if s[i] == '^':
					res = a ** b
				stack.append(res)
			else:
				stack.append(int(temp))
			i += 1
		return stack[-1]

	def calculate(self, s):
		exp = self.infix_postfix(s)
		res = self.calculation(exp)
		return res


class Solution:

	def calculate(self, s):
		if not s:
			return '0'
		(stack, num, sign) = ([], 0, '+')
		for i in range(len(s)):
			if s[i].isdigit():
				num = num * 10 + ord(s[i]) - ord('0')
			if not s[i].isdigit() and (not s[i].isspace()) or i == len(s) - 1:
				if sign == '-':
					stack.append(-num)
				elif sign == '+':
					stack.append(num)
				elif sign == '*':
					stack.append(stack.pop() * num)
				else:
					tmp = stack.pop()
					if tmp // num < 0 and tmp % num != 0:
						stack.append(tmp // num + 1)
					else:
						stack.append(tmp // num)
				sign = s[i]
				num = 0
		return sum(stack)


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def calculate(self, s):
		s = s.replace('/', '//')
		return eval(s)


class Solution:

	def calculate(self, tokens):

		def precedence(op):
			if op == '+' or op == '-':
				return 1
			if op == '*' or op == '/':
				return 2
			return 0

		def applyOp(a, b, op):
			if op == '-':
				return a - b
			if op == '+':
				return a + b
			if op == '*':
				return a * b
			if op == '/':
				return a // b

		def evaluate(tokens):
			n = len(tokens)
			operand = []
			operator = []
			i = 0
			while i < n:
				if tokens[i] == ' ':
					i += 1
					continue
				elif tokens[i] == '(':
					operator.append(tokens[i])
				elif tokens[i].isdigit():
					val = 0
					while i < n and tokens[i].isdigit():
						val = val * 10 + int(tokens[i])
						i += 1
					operand.append(val)
					i -= 1
				elif tokens[i] == ')':
					while len(operator) != 0 and operator[-1] != '(':
						val2 = operand.pop()
						val1 = operand.pop()
						op = operator.pop()
						val = applyOp(val1, val2, op)
						operand.append(val)
					operator.pop()
				else:
					while len(operator) != 0 and precedence(tokens[i]) <= precedence(operator[-1]):
						val2 = operand.pop()
						val1 = operand.pop()
						op = operator.pop()
						val = applyOp(val1, val2, op)
						operand.append(val)
					operator.append(tokens[i])
				i += 1
			while len(operator) != 0:
				val2 = operand.pop()
				val1 = operand.pop()
				op = operator.pop()
				val = applyOp(val1, val2, op)
				operand.append(val)
			return operand[-1]
		return evaluate(tokens)