



'''simple docstring'''







from __future__ import annotations

def  lowerCamelCase_					(       A_    ,				A_				):
	__lowerCamelCase		       =		get_failure_array(lowerCamelCase_				)

	# 2) Step through text searching for pattern
	__lowerCamelCase       ,	__lowerCamelCase		       =		0, 0  # index into text, pattern
	while i < len(lowerCamelCase_				):
		if pattern[j] == text[i]:
			if j == (len(lowerCamelCase_				) - 1):
				return True
			j += 1

		# if this is a prefix in our pattern
		# just go back far enough to continue
		elif j > 0:
			__lowerCamelCase		       =		failure[j - 1]
			continue
		i += 1
	return False

def  lowerCamelCase_					(       A_				):
	__lowerCamelCase		       =		[0]
	__lowerCamelCase		       =		0
	__lowerCamelCase		       =		1
	while j < len(lowerCamelCase_				):
		if pattern[i] == pattern[j]:
			i += 1
		elif i > 0:
			__lowerCamelCase		       =		failure[i - 1]
			continue
		j += 1
		failure.append(lowerCamelCase_				)
	return failure


if __name__ == "__main__":
				# Test 1)
				_UpperCamelCase					:  Tuple        ='abc1abc12'
				_UpperCamelCase					:  Union[str, Any]        ='alskfjaldsabc1abc1abc12k23adsfabcabc'
				_UpperCamelCase					:  Any        ='alskfjaldsk23adsfabcabc'
				assert kmp(pattern, texta) and not kmp(pattern, texta)

				# Test 2)
				_UpperCamelCase					:  int        ='ABABX'
				_UpperCamelCase					:  Optional[Any]        ='ABABZABABYABABX'
				assert kmp(pattern, text)

				# Test 3)
				_UpperCamelCase					:  int        ='AAAB'
				_UpperCamelCase					:  Dict        ='ABAAAAAB'
				assert kmp(pattern, text)

				# Test 4)
				_UpperCamelCase					:  List[Any]        ='abcdabcy'
				_UpperCamelCase					:  Union[str, Any]        ='abcxabcdabxabcdabcdabcy'
				assert kmp(pattern, text)

				# Test 5)
				_UpperCamelCase					:  int        ='aabaabaaa'
				assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]









from __future__ import annotations

from typing import Any






def     a     (		lowerCamelCase_							):






				'''simple docstring'''
				if not postfix_notation:
								return 0

				lowercase__  					=     {'''+''', '''-''', '''*''', '''/'''}
				lowercase__  					=     []

				for token in postfix_notation:
								if token in operations:
												lowercase__					,		lowercase__  					=     stack.pop(), stack.pop()
												if token == "+":
																stack.append(a + b							)
												elif token == "-":
																stack.append(a - b							)
												elif token == "*":
																stack.append(a * b							)
												else:
																if a * b < 0 and a % b != 0:
																				stack.append(a // b + 1							)
																else:
																				stack.append(a // b							)
								else:
												stack.append(int(lowerCamelCase_							)							)

				return stack.pop()


if __name__ == "__main__":
							import doctest

							doctest.testmod()




