https://school.programmers.co.kr/learn/courses/30/lessons/67257
initial
separate numbers from operators
First how do we separate the numbers from operators in "100-200*300-500+20"? First we initialise an empty list to store both of those. And a tmp variable of emtpy string to store the digits.
we can check if it is a digit or not via string.isdigit(). If it is digit, we store in our tmp variable to be added later to our list when we meet operator. When we meet operator, we append our tmp variable, which has been built with digits, and the current iterating variable (operator) to our lst. Don't forget to reininitialise tmp as empty string cuz if you don't, you will be builing upon the old numbers!
main logic
After separating the operators and numbers, I wasn’t sure which data structure to use to store them. Should I use a stack or list or queue? And that was just the first struggle. The main struggle is how on earth do you do 1 calculation of top priority first, and then the next priority and then the last priority? I had no idea but I knew marking the priority can be done via either permutations or bitmask like (0,2,1) , (2,1,0).
I searched up and found this idea the easiest and smartest. We can store each operator and number in a list. Then, the permutation we can take list of those 3 operators [*, +, -] and permutate them with length = 3. See my original thought of numbering priority like (0,2,1) is hard to implement but with this permutation, it is easier.
As we iterate through our permutation of operator priority, so the top priority will come first as our first iter. We are going to pop the front part of our list each time we iterate through this and add it to a stack. When we find that operator in our list, we compute that calculation by stack popping the last element and first element of list by popping. We then append this calculation to our stack. Then we reassign whatever we calculated in the stack back to this list. So effectively we have done the calculation of that top priority and we reassign our list with stack. We continue until we finish iterating through the priority permutation At the end, we will just have 1 final integer stored in our list and we get that value.
impt
notice I made a copy of lst for each iteration of permutation list of operators bcos we want the original list for each iteration.
we need to treat lst as a queue, not a stack because while we append numbers and operators into a stack, the way we are getting those numbers and operators should be in order of a queue sequentially from left to right, not a stack way.
solution
from collections import deque
from itertools import permutations
def solution(expression):
lst = []
tmp=''
for i in expression:
if i.isdigit():
tmp+=str(i)
else:
lst.append(tmp)
lst.append(i)
tmp=''
lst.append(tmp)
# for the main logic to be popped
kirk=deque(lst)
operations = list(permutations(['-','*','+'],3))
def calc(x,y,op):
if op=='*':
return str(int(x)*int(y))
elif op=='+':
return str(int(x)+int(y))
else:
return str(int(x)-int(y))
ans = []
for oper in operations:
lst = kirk.copy()
for op in oper:
stack=deque()
while lst:
tmp = lst.popleft()
if tmp==op:
stack.append(calc(stack.pop(),lst.popleft(),op))
else:
stack.append(tmp)
lst = stack
ans.append(abs(int(lst[0])))
ans.sort()
return (ans[-1])complexity
The time and space complexity of your code can be summarized as follows:
Time Complexity:
- Input Processing: O(n), where n is the length of the expression.
- Permutations Generation: O(1) (constant time as there are only six possible permutations).
- Calculation: O(n), where n is the length of the expression.
- Sorting: O(1) (constant time as there are only six elements to sort).
Overall Time Complexity: O(n)
Space Complexity:
- Input Processing Space: O(n)
- Permutations Space: O(1)
- Calculation Space: O(n)
- Result Space: O(1)
Overall Space Complexity: O(n)
In summary, your code has a time complexity of O(n) and a space complexity of O(n), where n is the length of the input expression. The time complexity is mainly influenced by the need to evaluate the expression, and the space complexity is determined by the storage of the input expression and temporary variables during the calculation. The space complexity is linear in the size of the input expression.
