মনে করুন আমাদের একটি বেসিক ক্যালকুলেটর ইম্প্লিমেন্ট করতে হবে যা একটি সিম্পল এক্সপ্রেশন স্ট্রিং ইভ্যালুয়েট করবে। এক্সপ্রেশন স্ট্রিং-এ শুধু নন-নেগেটিভ ইন্টিজার, অপারেটর +, -, *, / এবং খালি স্পেস থাকবে। ইন্টিজার ডিভিশনে কোশন্ট পর্বটিই নেওয়া হবে।
ইনপুট যদি "3+2*2" হয়, তবে আউটপুট হবে 7।
এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (স্ট্যাক ব্যবহার করে অপারেটর প্রসিডেন্স হ্যান্ডলিং):
stack := [], i := 0, x := ""s-এর প্রতিটি ক্যারেক্টারjজন্য:যদি
j != " ", তবেx += j
s := x, n := len(s)while i < n:যদি
s[i] == '/':i++, num, i = make_num(s, i)যদি
stack[-1] < 0, তবেstack[-1] = -(abs(stack[-1]) // num), অন্যথায়stack[-1] //= num
অন্যথায় যদি
s[i] == '*':i++, num, i = make_num(s, i)stack[-1] *= num
অন্যথায় যদি
s[i] == '-':i++, num, i = make_num(s, i)stack.append(-num)
অন্যথায় যদি
s[i] == '+':i++, num, i = make_num(s, i)stack.append(num)
অন্যথায় (সংখ্যা):
num, i = make_num(s, i)stack.append(num)i++
return sum(stack)
উদাহরণ
class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
stack = []
i = 0
x = ""
for j in s:
if j != " ":
x += j
s = x
n = len(s)
while i < n:
if s[i] == '/':
i += 1
num, i = self.make_num(s, i)
if stack[-1] < 0:
stack[-1] = -1 * (abs(stack[-1]) // num)
else:
stack[-1] = stack[-1] // num
elif s[i] == '*':
i += 1
num, i = self.make_num(s, i)
stack[-1] = stack[-1] * num
elif s[i] == '-':
i += 1
num, i = self.make_num(s, i)
stack.append(-num)
elif s[i] == '+':
i += 1
num, i = self.make_num(s, i)
stack.append(num)
else:
num, i = self.make_num(s, i)
stack.append(num)
i += 1
return sum(stack)
def make_num(self, s, i):
start = i
while i < len(s) and s[i] != '/' and s[i] != '*' and s[i] != '-' and s[i] != '+':
i += 1
return int(s[start:i]), i - 1
ইনপুট
"3+2*2"
আউটপুট
7
