150. Evaluate Reverse Polish Notation

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

• The valid operators are '+', '-', '*', and '/'.
• Each operand may be an integer or another expression.
• The division between two integers always truncates toward zero.
• There will not be any division by zero.
• The input represents a valid arithmetic expression in a reverse polish notation.
• The answer and all the intermediate calculations can be represented in a 32-bit integer.

 

풀이

 

case:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

후위 표현식을 계산해서 값을 리턴하는 문제이다 . 

 

리스트를 for문으로 순회하며 숫자라면 스택에 넣고, 사칙연산이라면 스택에 들어있는 숫자를 꺼내 연산해주면된다,

 

만들고나서 , 테스트케이스를 계속 돌렸는데, 빼기 연산과 나누기연산에서 값이 앞뒤가 바뀌어 계산되어서 틀렸었다.

 

더하기와 곱하기 연산은 순서 상관없이 곱하거나 더해주면 되기에 그냥 해줘도 되지만,

스택에 넣는 순서에 따라 계산되는 순서가 다르기에, 나누기와 빼기는 들어간 순서를 생각해서 계산식이 어떻게 만들어지는지 생각해서 만들어야한다.

 

 (5) + (-2) 라면 더해주기되면 음수 양수로 계산되어서 사오간없음 

 (5) - (-2) 라면 마이너스와 음수가 연산되며 양수로 바뀜 

 

연산되는 순서를 생각하자.

 

 

 

class Solution(object):
    def evalRPN(self, tokens):
        stack=[]
        oper = ['+','-','*','/']
        for i in tokens:
            if i not in oper:
                stack.append(int(i))
            else:
                num1 = stack.pop()
                num2 = stack.pop()
            
                if i == '-':
                    stack.append(int(num2)-int(num1))
                elif i == '+':
                    stack.append(num1+num2)
                elif i == '/':
                    stack.append(int(num2)/int(num1))
                elif i == '*':
                    stack.append(num1*num2)
                print(num1,num2,i)
        return stack[0]
                
        print(stack)
    
        


        """
        :type tokens: List[str]
        :rtype: int
        """

 

 

다른사람의 코드 

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stc=[]
        for a in tokens:
            if(a not in "+-*/"):
                stc.append(a)
            else:
                b2=stc.pop()
                b1=stc.pop()
                x=int(eval(b1+a+b2))
                stc.append(str(x))
        return int(stc[0])

 

동일하게 스택에 숫자를 넣은 뒤 연산자가 나온다면, 스택에서 2개의 숫자를 팝해서 eval함수로 연산자와 합쳐 계산되게 만든다.