Given string S representing a postfix expression, the task is to evaluate the expression and find the final value. Operators will only include the basic arithmetic operators like *, /, + and -.
 
Example 1:
Input: S = "231*+9-"
Output: -4
Explanation:
After solving the given expression, 
we have -4 as result.
Example 2:
Input: S = "123+*8-"
Output: -3
Explanation:
After solving the given postfix 
expression, we have -3 as result.
Your Task:
You do not need to read input or print anything. Complete the function evaluatePostfixExpression() that takes the string S denoting the expression as input parameter and returns the evaluated value.
Expected Time Complexity: O(|S|)
Expected Auixilliary Space: O(|S|)
Constraints:
1 ≤ |S| ≤ 10^{5}
0 ≤ |S_{i}|≤ 9 (And given operators)

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)

Starter code:
#User function Template for python3

class Solution:
    
    #Function to evaluate a postfix expression.
    def evaluatePostfix(self, S):
        #code here

Solutions:
class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for i in range(len(S)):
			if S[i] in ['+', '-', '/', '*']:
				y = stack.pop()
				x = stack.pop()
				if S[i] == '+':
					stack.append(x + y)
				elif S[i] == '-':
					stack.append(x - y)
				elif S[i] == '*':
					stack.append(x * y)
				elif S[i] == '/':
					stack.append(x // y)
			else:
				stack.append(int(S[i]))
		return stack[-1]


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for i in S:
			if i.isdigit() is True:
				stack.append(i)
			else:
				a = int(stack.pop())
				b = int(stack.pop())
				if i == '+':
					res = b + a
				elif i == '-':
					res = b - a
				elif i == '*':
					res = b * a
				else:
					res = b // a
				stack.append(res)
		return res


class Solution:

	def evaluatePostfix(self, s):
		stack = []
		for i in s:
			if i in ['+', '*', '/', '-']:
				(y, x) = (stack.pop(), stack.pop())
				if i == '+':
					stack.append(x + y)
				elif i == '*':
					stack.append(x * y)
				elif i == '-':
					stack.append(x - y)
				else:
					stack.append(x // y)
			else:
				stack.append(int(i))
		return stack[-1]


class Solution:

	def evaluatePostfix(self, S):
		st = []
		ans = 0
		for i in S:
			if i.isdigit():
				st.append(i)
			else:
				if i == '/':
					i = '//'
				second = st.pop()
				first = st.pop()
				st.append(str(eval(first + i + second)))
		return int(st.pop())


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for i in S:
			if i in ['1', '2', '3', '4', '5', '6', '7', '8', '9', '0']:
				stack.append(int(i))
			else:
				op1 = stack.pop()
				op2 = stack.pop()
				if i == '/':
					stack.append(op2 // op1)
				if i == '*':
					stack.append(op1 * op2)
				if i == '+':
					stack.append(op1 + op2)
				if i == '-':
					stack.append(op2 - op1)
		return stack[-1]


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for i in S:
			if i.isdigit():
				stack.append(i)
			else:
				a = int(stack.pop())
				b = int(stack.pop())
				if i == '+':
					stack.append(a + b)
				elif i == '-':
					stack.append(b - a)
				elif i == '*':
					stack.append(a * b)
				else:
					stack.append(b // a)
		return sum(stack)


class Solution:

	def evaluatePostfix(self, S):
		S = S + '$'
		st = []
		for i in S:
			if i == '$':
				return st[-1]
			if i.isdigit():
				st.append(i)
			else:
				a = st.pop()
				b = st.pop()
				if i == '*':
					c = int(b) * int(a)
				elif i == '+':
					c = int(b) + int(a)
				elif i == '-':
					c = int(b) - int(a)
				else:
					c = int(b) / int(a)
				st.append(c)


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for i in S:
			if i.isdigit():
				stack.append(i)
			else:
				val1 = int(stack.pop())
				val2 = int(stack.pop())
				if i == '+':
					stack.append(val2 + val1)
				elif i == '-':
					stack.append(val2 - val1)
				elif i == '*':
					stack.append(val2 * val1)
				else:
					stack.append(val2 // val1)
		return sum(stack)


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for i in S:
			if i not in ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']:
				eva = 0
				a = int(stack.pop(-1))
				b = int(stack.pop(-1))
				if i == '+':
					eva = a + b
				elif i == '-':
					eva = b - a
				elif i == '*':
					eva = a * b
				elif i == '/':
					eva = b // a
				stack.append(eva)
			else:
				stack.append(i)
		return stack[-1]


class Solution:

	def evaluatePostfix(self, s):
		st = []
		for i in s:
			if i in '0123456789':
				st.append(i)
			else:
				p2 = st.pop()
				p1 = st.pop()
				res = eval(p1 + i + p2)
				st.append(str(int(res)))
		return st[-1]


class Solution:

	def evaluatePostfix(self, S):
		st = []
		hashmap = {'*', '+', '-', '/'}
		for i in S:
			if i in hashmap:
				val1 = st.pop()
				val2 = st.pop()
				if i == '+':
					st.append(val2 + val1)
				elif i == '-':
					st.append(val2 - val1)
				elif i == '*':
					st.append(val2 * val1)
				elif i == '/':
					st.append(val2 // val1)
			else:
				st.append(int(i))
		return sum(st)


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		hashset = {'*', '/', '+', '-'}
		for i in S:
			if i in hashset:
				a = stack.pop()
				b = stack.pop()
				if i == '*':
					stack.append(b * a)
				elif i == '/':
					stack.append(b // a)
				elif i == '+':
					stack.append(b + a)
				else:
					stack.append(b - a)
			else:
				stack.append(int(i))
		return stack[0]


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		top = -1
		for i in S:
			if i >= '0' and i <= '9':
				stack.append(int(i))
				top += 1
			else:
				y = stack.pop()
				top -= 1
				x = stack.pop()
				top -= 1
				if i == '+':
					stack.append(x + y)
					top += 1
				if i == '-':
					stack.append(x - y)
					top += 1
				if i == '*':
					stack.append(x * y)
					top += 1
				if i == '/':
					stack.append(x // y)
					top += 1
		return stack[0]


class Solution:

	def evaluatePostfix(self, S):
		st = []
		for i in S:
			if i.isdigit():
				st.append(int(i))
			elif len(st) > 1:
				if i == '+':
					st.append(st.pop(-1) + st.pop(-1))
				elif i == '-':
					st.append(-st.pop(-1) + st.pop(-1))
				elif i == '*':
					st.append(st.pop(-1) * st.pop(-1))
				elif i == '/':
					s = st.pop(-1)
					f = st.pop(-1)
					st.append(f // s)
		return st.pop(-1)


import operator

class Solution:

	def evaluatePostfix(self, S):
		stk = []
		r = 0
		for i in range(len(S)):
			if S[i] in ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']:
				stk.append(int(S[i]))
			else:
				r1 = stk.pop()
				r2 = stk.pop()
				if S[i] == '*':
					op = operator.mul(r2, r1)
				elif S[i] == '-':
					op = operator.sub(r2, r1)
				elif S[i] == '+':
					op = operator.add(r2, r1)
				else:
					op = operator.truediv(r2, r1)
				op = int(op)
				stk.append(op)
		return stk[-1]


class Solution:

	def ev(self, a, b, c):
		if c == '+':
			return a + b
		elif c == '-':
			return b - a
		elif c == '*':
			return a * b
		else:
			return b // a

	def evaluatePostfix(self, S):
		s = []
		for i in range(0, len(S)):
			if S[i].isalnum():
				s.append(int(S[i]))
			else:
				s.append(self.ev(s.pop(), s.pop(), S[i]))
		return s[-1]


class Solution:

	def evaluatePostfix(self, s):
		postfix = []
		for i in range(len(s)):
			if s[i] == '+':
				a1 = postfix.pop()
				a2 = postfix.pop()
				postfix.append(a1 + a2)
			elif s[i] == '-':
				a1 = postfix.pop()
				a2 = postfix.pop()
				postfix.append(a2 - a1)
			elif s[i] == '*':
				a1 = postfix.pop()
				a2 = postfix.pop()
				postfix.append(a1 * a2)
			elif s[i] == '/':
				a1 = postfix.pop()
				a2 = postfix.pop()
				postfix.append(a2 // a1)
			else:
				postfix.append(int(s[i]))
		return postfix.pop()


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for i in S:
			if i == '*':
				(n, m) = (stack.pop(), stack.pop())
				stack.append(n * m)
			elif i == '/':
				(n, m) = (stack.pop(), stack.pop())
				stack.append(m // n)
			elif i == '+':
				(n, m) = (stack.pop(), stack.pop())
				stack.append(n + m)
			elif i == '-':
				(n, m) = (stack.pop(), stack.pop())
				stack.append(m - n)
			else:
				stack.append(int(i))
		return stack[-1]


class Solution:

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

	def evaluatePostfix(self, S):
		stk = []
		ans = 0
		for ch in S:
			if ch in ('+', '-', '*', '/'):
				a = stk.pop()
				b = stk.pop()
				res = self.do_maths(b, a, ch)
				stk.append(res)
			else:
				stk.append(int(ch))
		return stk.pop()


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for ch in S:
			if ch == '*' or ch == '+' or ch == '-' or (ch == '/'):
				first = stack.pop()
				second = stack.pop()
				if ch == '*':
					result = first * second
				elif ch == '/':
					result = second // first
				elif ch == '+':
					result = second + first
				else:
					result = second - first
				stack.append(result)
			else:
				stack.append(int(ch))
		return stack[-1]


class Solution:

	def evaluatePostfix(self, S):
		stk = []
		for i in S:
			if i == '*':
				A = stk.pop()
				B = stk.pop()
				stk.append(B * A)
			elif i == '/':
				A = stk.pop()
				B = stk.pop()
				stk.append(B // A)
			elif i == '-':
				A = stk.pop()
				B = stk.pop()
				stk.append(B - A)
			elif i == '+':
				A = stk.pop()
				B = stk.pop()
				stk.append(B + A)
			else:
				stk.append(int(i))
		return stk[-1]


class Solution:

	def evaluatePostfix(self, S):
		k = '+-*/'
		arr = []
		s = S[:]
		for i in range(len(s)):
			if s[i].isnumeric():
				arr.append(s[i])
			if s[i] in k:
				a = arr.pop()
				b = arr.pop()
				if s[i] == '*':
					c = int(b) * int(a)
					arr.append(c)
				elif s[i] == '+':
					c = int(b) + int(a)
					arr.append(c)
				elif s[i] == '-':
					c = int(b) - int(a)
					arr.append(c)
				elif s[i] == '/':
					c = int(b) / int(a)
					arr.append(c)
		return arr[0]


class Solution:

	def evaluatePostfix(self, S):
		a = []
		for i in S:
			if i.isnumeric():
				a.append(int(i))
			elif i == '*':
				m = a[-1] * a[-2]
				a.pop(-1)
				a.pop(-1)
				a.append(int(m))
			elif i == '+':
				m = a[-1] + a[-2]
				a.pop(-1)
				a.pop(-1)
				a.append(int(m))
			elif i == '-':
				m = a[-2] - a[-1]
				a.pop(-1)
				a.pop(-1)
				a.append(int(m))
			elif i == '/':
				m = a[-2] / a[-1]
				a.pop(-1)
				a.pop(-1)
				a.append(int(m))
		return int(a[0])


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for item in S:
			if item.isdigit():
				stack.append(item)
			else:
				item1 = stack.pop()
				item2 = stack.pop()
				stack.append(str(int(eval(item2 + item + item1))))
		return stack.pop()


class Solution:

	def evaluatePostfix(self, S):
		stk = []
		for i in S:
			if i == '+':
				stk.append(stk.pop() + stk.pop())
			elif i == '-':
				(a, b) = (stk.pop(), stk.pop())
				stk.append(b - a)
			elif i == '*':
				stk.append(stk.pop() * stk.pop())
			elif i == '/':
				(a, b) = (stk.pop(), stk.pop())
				stk.append(int(b / a))
			else:
				stk.append(int(i))
		return stk[-1]


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for i in S:
			if i != '+' and i != '*' and (i != '-') and (i != '/'):
				stack.append(i)
			else:
				n1 = int(stack.pop())
				n2 = int(stack.pop())
				if i == '+':
					stack.append(n1 + n2)
				elif i == '-':
					stack.append(n2 - n1)
				elif i == '*':
					stack.append(n1 * n2)
				elif i == '/':
					stack.append(n2 / n1)
		return stack[-1]


def post_fix_evaluation(input_string):
	operand_stack = []
	n = len(input_string)
	for i in range(n):
		element = input_string[i]
		if is_integer(element):
			operand_stack.append(int(element))
		else:
			pop_do_operation(operand_stack, element)
	return operand_stack[0]

def performOperation(operand_1: int, operand_2: int, operator: str):
	if operator == '+':
		return operand_1 + operand_2
	elif operator == '-':
		return operand_1 - operand_2
	elif operator == '*':
		return operand_1 * operand_2
	else:
		return int(operand_1 / operand_2)

def pop_do_operation(operand_stack: [], operator: str):
	operand_2 = operand_stack.pop(-1)
	operand_1 = operand_stack.pop(-1)
	new_element = performOperation(operand_1, operand_2, operator)
	operand_stack.append(new_element)

def is_integer(element):
	return ord('0') <= ord(element) <= ord('9')

class Solution:

	def evaluatePostfix(self, S):
		return post_fix_evaluation(S)


class Solution:

	def evaluatePostfix(self, S):
		op = {'*': lambda x, y: x * y, '+': lambda x, y: x + y, '-': lambda x, y: x - y, '/': lambda x, y: x / y}
		stack = []
		n = len(S)
		for i in range(0, n):
			if S[i].isdigit():
				stack.append(S[i])
			else:
				y = int(stack.pop())
				x = int(stack.pop())
				z = op[S[i]](x, y)
				stack.append(z)
		return stack.pop()


class Solution:

	def evaluatePostfix(self, S):
		st = []
		for i in S:
			if i in ['+', '-', '*', '/']:
				op2 = int(st.pop())
				op1 = int(st.pop())
				if i == '+':
					st.append(op1 + op2)
				elif i == '-':
					st.append(op1 - op2)
				elif i == '*':
					st.append(op1 * op2)
				elif i == '/':
					st.append(op1 / op2)
			else:
				st.append(i)
		return st[-1]


class Solution:

	def evaluatePostfix(self, S):
		expr = ['*', '/', '+', '-']
		arr = []
		for i in S:
			if i in expr:
				op2 = int(arr.pop())
				op1 = int(arr.pop())
				if i == '*':
					result = op1 * op2
				elif i == '/':
					result = op1 / op2
				elif i == '+':
					result = op1 + op2
				else:
					result = op1 - op2
				arr.append(result)
			else:
				arr.append(i)
		return arr.pop()


class Solution:

	def evaluatePostfix(self, S):
		st = []
		n = len(S)
		for i in range(n):
			if not S[i] in '+-/*':
				st.append(S[i])
			else:
				a = int(st.pop())
				b = int(st.pop())
				if S[i] == '+':
					tmpAns = b + a
				if S[i] == '-':
					tmpAns = b - a
				if S[i] == '/':
					tmpAns = b / a
				if S[i] == '*':
					tmpAns = b * a
				st.append(tmpAns)
		return st[-1]


class Solution:

	def evaluatePostfix(self, S):
		s = []
		for i in S:
			if i.isdigit():
				s.append(int(i))
			elif i == '+':
				x = s.pop()
				y = s.pop()
				s.append(x + y)
			elif i == '-':
				x = s.pop()
				y = s.pop()
				s.append(y - x)
			elif i == '*':
				x = s.pop()
				y = s.pop()
				s.append(x * y)
			elif i == '/':
				x = s.pop()
				y = s.pop()
				s.append(y // x)
		return s[0]


class Solution:

	def evaluatePostfix(self, S):
		stk = []
		s1 = '*/+-'
		for i in S:
			if i not in s1:
				stk.append(int(i))
			else:
				x = stk.pop()
				y = stk.pop()
				if i == '*':
					res = x * y
				elif i == '+':
					res = x + y
				elif i == '-':
					res = y - x
				else:
					res = y // x
				stk.append(res)
		return stk[-1]


class Solution:

	def evaluatePostfix(self, S):
		x = ['+', '-', '/', '*']
		stack = []
		for i in S:
			if i in x:
				a = stack.pop()
				b = stack.pop()
				r = b + i + a
				res = int(eval(r))
				stack.append(str(res))
			else:
				stack.append(i)
		return stack.pop()


class Solution:

	def evaluatePostfix(self, s):
		stack = []
		for c in s:
			if c == '+' or c == '/' or c == '*' or (c == '-'):
				op2 = int(stack.pop())
				op1 = int(stack.pop())
				if c == '+':
					r = op1 + op2
				elif c == '-':
					r = op1 - op2
				elif c == '*':
					r = op1 * op2
				else:
					r = op1 // op2
				stack.append(r)
			else:
				stack.append(int(c))
		return stack[0]


class Solution:

	def evaluatePostfix(self, S):
		x = []
		op = {'*', '/', '+', '-'}
		for i in S:
			if i in op:
				a = x.pop()
				b = x.pop()
				if i == '*':
					x.append(b * a)
				elif i == '/':
					x.append(b // a)
				elif i == '+':
					x.append(b + a)
				else:
					x.append(b - a)
			else:
				x.append(int(i))
		return x[0]


class Solution:

	def evaluatePostfix(self, S):
		l = list(S)
		operators = ['*', '+', '-', '/']
		operands = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
		stack = []
		for i in range(len(l)):
			if str(l[i]) not in operators:
				stack.append(int(l[i]))
			else:
				s1 = stack.pop()
				s2 = stack.pop()
				if str(l[i]) == '-':
					val = s2 - s1
				elif str(l[i]) == '+':
					val = s1 + s2
				elif str(l[i]) == '*':
					val = s1 * s2
				elif str(l[i]) == '/':
					val = s2 // s1
				stack.append(val)
		return stack[-1]


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for i in S:
			if i == '+' or i == '/' or i == '*' or (i == '-'):
				a = stack.pop()
				b = stack.pop()
				if i == '/':
					p = '//'
					stack.append(str(eval(b + p + a)))
				else:
					stack.append(str(eval(b + i + a)))
			else:
				stack.append(i)
		re = stack.pop()
		return re


class Solution:

	def evaluatePostfix(self, s):
		st = []
		for i in s:
			if i.isdigit():
				st.append(i)
			else:
				op1 = int(st.pop())
				op2 = int(st.pop())
				if i == '+':
					ans = op2 + op1
				elif i == '-':
					ans = op2 - op1
				elif i == '*':
					ans = op2 * op1
				elif i == '/':
					ans = op2 / op1
				st.append(ans)
		return st.pop()


from queue import LifoQueue as Stack

class Solution:

	def evaluatePostfix(self, S):
		stack = Stack()
		for char in S:
			if char in '*/+-':
				(operand2, operand1) = (stack.get(), stack.get())
				result = str(int(eval(operand1 + char + operand2)))
				stack.put(result)
			else:
				stack.put(char)
		return int(stack.get())


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for ele in S:
			if ele.isalnum():
				stack.append(ele)
				continue
			if len(stack) >= 2:
				sec = int(stack.pop())
				first = int(stack.pop())
			else:
				return -1
			if ele == '*':
				stack.append(first * sec)
			elif ele == '+':
				stack.append(first + sec)
			elif ele == '-':
				stack.append(first - sec)
			elif ele == '/':
				stack.append(first // sec)
		return stack[0] if stack else -1


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		operators = ('+', '-', '*', '/')
		for item in S:
			if item not in operators:
				stack.append(item)
			else:
				first = int(stack.pop())
				second = int(stack.pop())
				if item == '+':
					stack.append(second + first)
				elif item == '-':
					stack.append(second - first)
				elif item == '*':
					stack.append(second * first)
				elif item == '/':
					stack.append(second / first)
		return stack[0]


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		ans = None
		for i in S:
			if i == '*':
				t1 = stack.pop()
				t2 = stack.pop()
				stack.append(t1 * t2)
			elif i == '+':
				t1 = stack.pop()
				t2 = stack.pop()
				stack.append(t1 + t2)
			elif i == '-':
				t1 = stack.pop()
				t2 = stack.pop()
				stack.append(t2 - t1)
			elif i == '/':
				t1 = stack.pop()
				t2 = stack.pop()
				stack.append(t2 // t1)
			else:
				stack.append(int(i))
		return stack.pop()


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for i in S:
			if i.isdigit():
				stack.append(int(i))
			elif i == '*':
				stack.append(int(stack.pop(-2) * stack.pop()))
			elif i == '/':
				stack.append(int(stack.pop(-2) / stack.pop()))
			elif i == '+':
				stack.append(int(stack.pop(-2) + stack.pop()))
			elif i == '-':
				stack.append(int(stack.pop(-2) - stack.pop()))
		return stack[0]


class Solution:

	def evaluatePostfix(self, S):

		def fun(x, y, oper):
			if oper == '+':
				return x + y
			if oper == '-':
				return x - y
			if oper == '*':
				return x * y
			if oper == '/':
				return x // y
		s = []
		for i in S:
			if i.isdigit():
				s.append(int(i))
			else:
				y = s.pop()
				x = s.pop()
				res = fun(x, y, i)
				s.append(res)
		return s.pop()


class Solution:

	def evaluatePostfix(self, S):
		l = ['+', '-', '*', '/']
		s1 = []
		for i in S:
			if i not in l:
				s1.append(i)
			else:
				o1 = int(s1.pop())
				o2 = int(s1.pop())
				if i == '+':
					s1.append(o1 + o2)
				elif i == '-':
					s1.append(o2 - o1)
				elif i == '*':
					s1.append(o1 * o2)
				else:
					try:
						s1.append(int(o2 // o1))
					except:
						return int(o2 // o1)
		return s1.pop()


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		res = 0
		for i in S:
			if i.isnumeric():
				stack.append(int(i))
			else:
				a = stack.pop()
				b = stack.pop()
				if i == '+':
					res = b + a
				if i == '*':
					res = b * a
				if i == '-':
					res = b - a
				if i == '/':
					res = b // a
				stack.append(res)
		return stack[-1]


class Solution:

	def evaluatePostfix(self, S):
		(stack, n) = ([], len(S))
		for i in range(n):
			if S[i] == '*':
				op2 = stack.pop()
				op1 = stack.pop()
				stack.append(op1 * op2)
			elif S[i] == '+':
				op2 = stack.pop()
				op1 = stack.pop()
				stack.append(op1 + op2)
			elif S[i] == '-':
				op2 = stack.pop()
				op1 = stack.pop()
				stack.append(op1 - op2)
			elif S[i] == '/':
				op2 = stack.pop()
				op1 = stack.pop()
				stack.append(op1 // op2)
			else:
				stack.append(int(S[i]))
		return stack.pop() if stack else 0


class Solution:

	def evaluatePostfix(self, s):
		stack = list()
		for char in s:
			if char == '+':
				op2 = stack.pop()
				op1 = stack.pop()
				stack.append(op1 + op2)
			elif char == '-':
				op2 = stack.pop()
				op1 = stack.pop()
				stack.append(op1 - op2)
			elif char == '*':
				op2 = stack.pop()
				op1 = stack.pop()
				stack.append(op1 * op2)
			elif char == '/':
				op2 = stack.pop()
				op1 = stack.pop()
				stack.append(int(op1 / op2))
			else:
				stack.append(int(char))
		return stack.pop()


def get_res(a, b, symbol):
	if symbol == '+':
		return a + b
	elif symbol == '-':
		return a - b
	elif symbol == '*':
		return a * b
	else:
		return a // b

class Solution:

	def evaluatePostfix(self, S):
		exp = list(S)
		stack = []
		for i in exp:
			if i.isdigit():
				stack.append(int(i))
			else:
				op1 = stack.pop()
				op2 = stack.pop()
				res = get_res(op2, op1, i)
				stack.append(res)
		return stack[-1]


class Solution:

	def evaluatePostfix(self, S):
		temp = []
		for i in S:
			if i.isdigit():
				temp.append(i)
			elif i in ['*', '+', '-', '/']:
				b = int(temp.pop())
				a = int(temp.pop())
				if i == '*':
					ans = a * b
				elif i == '/':
					ans = a // b
				elif i == '-':
					ans = a - b
				else:
					ans = a + b
				temp.append(ans)
		return temp.pop()


class Solution:

	def evaluatePostfix(self, S):
		li = []
		for i in S:
			if i not in '*/+-':
				li.insert(0, i)
			elif i == '*':
				p2 = li.pop(0)
				p1 = li.pop(0)
				li.insert(0, int(p1) * int(p2))
			elif i == '/':
				p2 = li.pop(0)
				p1 = li.pop(0)
				li.insert(0, int(p1) / int(p2))
			elif i == '+':
				p2 = li.pop(0)
				p1 = li.pop(0)
				li.insert(0, int(p1) + int(p2))
			elif i == '-':
				p2 = li.pop(0)
				p1 = li.pop(0)
				li.insert(0, int(p1) - int(p2))
		res = li.pop(0)
		return res


class Solution:

	def evaluatePostfix(self, S):
		st = []
		for i in S:
			if i in '0123456789':
				st.append(i)
			elif i in '+-/*':
				op1 = st.pop()
				op2 = st.pop()
				res = eval(op2 + i + op1)
				st.append(str(int(res)))
		return ''.join(st)


class Solution:

	def evaluatePostfix(self, S):
		a = []
		for s in S:
			if s == '*' or s == '/' or s == '+' or (s == '-'):
				x = a.pop()
				y = a.pop()
				z = eval(str(y) + s + str(x))
				a.append(int(z))
				s = s[1:]
			else:
				a.append(s[0])
				s = s[1:]
		res = a[0]
		return res


class Solution:

	def evaluatePostfix(self, s):
		stack = list()
		n = len(s)
		for i in range(n):
			if s[i] == '+':
				op2 = stack.pop()
				op1 = stack.pop()
				stack.append(int(op1 + op2))
			elif s[i] == '-':
				op2 = stack.pop()
				op1 = stack.pop()
				stack.append(int(op1 - op2))
			elif s[i] == '*':
				op2 = stack.pop()
				op1 = stack.pop()
				stack.append(int(op1 * op2))
			elif s[i] == '/':
				op2 = stack.pop()
				op1 = stack.pop()
				stack.append(int(op1 / op2))
			else:
				stack.append(int(s[i]))
		return stack.pop()


class Solution:

	def evaluatePostfix(self, s):
		stack = []
		for c in s:
			if c in '+-*/':
				if c == '+':
					stack.append(stack.pop() + stack.pop())
				if c == '-':
					stack.append(-stack.pop() + stack.pop())
				if c == '*':
					stack.append(stack.pop() * stack.pop())
				if c == '/':
					t = stack.pop()
					u = stack.pop()
					stack.append(u // t)
			elif c in '0123456789':
				stack.append(int(c))
		return stack[0]


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for i in range(len(S)):
			if '0' <= S[i] <= '9':
				stack.append(S[i])
			else:
				op2 = int(stack.pop())
				op1 = int(stack.pop())
				if S[i] == '+':
					res = op1 + op2
				if S[i] == '-':
					res = op1 - op2
				if S[i] == '*':
					res = op1 * op2
				if S[i] == '/':
					res = op1 // op2
				stack.append(res)
		return stack[-1]


class Solution:

	def evaluatePostfix(self, S):
		symbol = ['*', '+', '-', '/']
		a = []
		for i in S:
			if i not in symbol:
				a.append(int(i))
			else:
				a1 = a.pop()
				a2 = a.pop()
				if i == '*':
					a.append(a2 * a1)
				elif i == '+':
					a.append(a2 + a1)
				elif i == '-':
					a.append(a2 - a1)
				elif i == '/':
					a.append(a2 // a1)
		return a[0]


import queue

class Solution:

	def evaluatePostfix(self, S):
		stack = queue.LifoQueue()
		for ele in S:
			if ele == '*' or ele == '/' or ele == '+' or (ele == '-'):
				a = stack.get()
				b = stack.get()
				if ele == '*':
					x = b * a
				elif ele == '/':
					x = b // a
				elif ele == '+':
					x = b + a
				else:
					x = b - a
				stack.put(x)
			else:
				stack.put(int(ele))
		return stack.get()


class Solution:

	def evaluatePostfix(self, S):
		temp = []
		for i in range(len(S)):
			if S[i] == '/':
				a = int(temp.pop())
				b = int(temp.pop())
				temp.append(b / a)
			elif S[i] == '*':
				a = int(temp.pop())
				b = int(temp.pop())
				temp.append(a * b)
			elif S[i] == '-':
				a = int(temp.pop())
				b = int(temp.pop())
				temp.append(b - a)
			elif S[i] == '+':
				a = int(temp.pop())
				b = int(temp.pop())
				temp.append(a + b)
			else:
				temp.append(S[i])
		return temp[0]


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for i in S:
			if i.isdigit():
				stack.append(i)
			else:
				val1 = stack.pop()
				val2 = stack.pop()
				if i == '/':
					p = '//'
					stack.append(str(eval(val2 + p + val1)))
				else:
					stack.append(str(eval(val2 + i + val1)))
		return stack.pop()


class Solution:

	def evaluatePostfix(self, S):
		st = []
		op = ['+', '-', '*', '/']
		for i in S:
			if i in op:
				a = st[-1]
				st.pop()
				a = int(a)
				b = st[-1]
				st.pop()
				b = int(b)
				if i == '+':
					st.append(b + a)
				if i == '-':
					st.append(b - a)
				if i == '*':
					st.append(b * a)
				if i == '/':
					st.append(int(b / a))
			else:
				st.append(i)
		return st[-1]


class Solution:

	def evaluatePostfix(self, S):
		op = ['*', '+', '-', '/']
		stk = []
		for c in S:
			if c not in op:
				stk.append(c)
			else:
				optr = c
				op2 = stk.pop()
				op1 = stk.pop()
				res = int(eval(str(op1) + str(optr) + str(op2)))
				stk.append(res)
		x = stk.pop()
		return x


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for chr in S:
			if chr in '+-/*':
				if len(stack) < 2:
					return 'stack underflow'
				else:
					a = stack.pop()
					b = stack.pop()
					result = eval(str(b) + chr + str(a))
					stack.append(int(result))
			else:
				stack.append(chr)
		return stack.pop()


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for item in S:
			if item != '*' and item != '/' and (item != '+') and (item != '-'):
				stack.append(item)
			else:
				item1 = int(stack.pop())
				item2 = int(stack.pop())
				if item == '*':
					stack.append(item1 * item2)
				elif item == '/':
					stack.append(item2 // item1)
				elif item == '+':
					stack.append(item1 + item2)
				else:
					stack.append(item2 - item1)
		return stack.pop()


class Solution:

	def evaluatePostfix(self, s):
		r = 0
		l = []
		for i in s:
			if i in ['1', '2', '3', '4', '5', '6', '7', '8', '9', '0']:
				l.append(int(i))
			else:
				b = l.pop()
				a = l.pop()
				if i == '*':
					r = a * b
				if i == '+':
					r = a + b
				if i == '-':
					r = a - b
				if i == '/':
					r = a // b
				l.append(r)
		return l[-1]


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for ch in S:
			if ifOperand(ch):
				a = stack.pop()
				b = stack.pop()
				if ch == '-':
					stack.append(int(b) - int(a))
				if ch == '+':
					stack.append(int(b) + int(a))
				if ch == '*':
					stack.append(int(b) * int(a))
				if ch == '/':
					stack.append(int(b) // int(a))
			else:
				stack.append(ch)
		return stack[-1]

def ifOperand(ch):
	return ch == '*' or ch == '+' or ch == '/' or (ch == '-')


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for char in S:
			if char.isnumeric():
				stack.append(char)
			else:
				second_num = int(stack.pop(-1))
				first_num = int(stack.pop(-1))
				if char == '*':
					ans = first_num * second_num
					stack.append(ans)
				elif char == '+':
					ans = first_num + second_num
					stack.append(ans)
				elif char == '-':
					ans = first_num - second_num
					stack.append(ans)
				elif char == '/':
					ans = first_num / second_num
					stack.append(ans)
		return stack.pop(-1)


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		allOperators = set(['+', '-', '*', '/', '^', '(', ')'])
		for i in range(0, len(S)):
			if S[i] not in allOperators:
				stack.append(S[i])
			else:
				a = stack[-1]
				stack.pop()
				a = int(a)
				b = stack[-1]
				stack.pop()
				b = int(b)
				if S[i] == '+':
					stack.append(b + a)
				if S[i] == '-':
					stack.append(b - a)
				if S[i] == '*':
					stack.append(b * a)
				if S[i] == '/':
					stack.append(b / a)
		return stack[-1]


class Stack:

	def __init__(self, maxsize):
		self.maxsize = maxsize
		self.top = -1
		self.arr = []

	def empty(self):
		return self.top == -1

	def full(self):
		return self.top == self.maxsize

	def push(self, data):
		if self.full():
			return 'Stack is full'
		self.top += 1
		self.arr.append(data)

	def peek(self):
		if self.empty():
			return 'Stack is empty'
		return self.arr[self.top]

	def pop(self):
		if self.empty():
			return 'Stack is empty'
		top_ele = self.arr.pop()
		self.top -= 1
		return top_ele

class Solution:

	def pred(self, sym):
		if sym == '*' or sym == '/':
			return 3
		if sym == '+' or sym == '-':
			return 2
		if sym == '#':
			return 1

	def op(self, l, r, o):
		if o == '*':
			return l * r
		if o == '/':
			return l // r
		if o == '+':
			return l + r
		if o == '-':
			return l - r

	def evaluatePostfix(self, S):
		post_arr = []
		for s in S:
			if s in ('*', '/', '+', '-'):
				right = post_arr.pop()
				left = post_arr.pop()
				post_arr.append(self.op(int(left), int(right), s))
			else:
				post_arr.append(s)
		res = post_arr.pop()
		if res == -0:
			return 0
		return res


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for i in S:
			if i in ['1', '2', '3', '4', '5', '6', '7', '8', '9', '0']:
				stack.append(int(i))
			else:
				pop1 = stack.pop()
				pop2 = stack.pop()
			if i == '*':
				value = pop2 * pop1
				stack.append(value)
			elif i == '+':
				value = pop2 + pop1
				stack.append(value)
			elif i == '-':
				value = pop2 - pop1
				stack.append(value)
			elif i == '/':
				value = pop2 // pop1
				stack.append(value)
		return stack[-1]


class Solution:

	def evaluatePostfix(self, S):
		stack = []
		for i in S:
			if i in ['*', '/', '+', '-']:
				y = stack.pop()
				x = stack.pop()
				if i == '*':
					stack.append(int(x) * int(y))
				elif i == '/':
					stack.append(int(x) / int(y))
				elif i == '+':
					stack.append(int(x) + int(y))
				elif i == '-':
					stack.append(int(x) - int(y))
			else:
				stack.append(i)
		return stack[0]


class Solution:

	def evaluatePostfix(self, S):
		result = 0
		stack = []
		for i in S:
			if i in ('0', '1', '2', '3', '4', '5', '6', '7', '8', '9'):
				stack.append(int(i))
			else:
				first_value = stack.pop()
				second_value = stack.pop()
				if i == '+':
					result = second_value + first_value
				if i == '-':
					result = second_value - first_value
				if i == '*':
					result = second_value * first_value
				if i == '/':
					result = second_value // first_value
				stack.append(result)
		return stack.pop()