【leetcode】Evaluate Reverse Polish Notation(middle)

8999 단어 LeetCode
Evaluate the value of an arithmetic expression in  Reverse Polish Notation .
Valid operators are  +-*/ . Each operand may be an integer or another expression.
Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9

  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

 
생각:
제목은 표현식이 항상 두 개의 조작수를 먼저 제시한 다음에 대응하는 조작부호를 제시한다는 뜻이다.이런 표현식을 제시한 후에 표현식에 대응하는 값을 구한다.
어려운 점은 뒤에 있는 조작부호의 조작수도 표현식이라는 것이다.해결 방법은 창고nums로 사용하지 않은 모든 조작수를 저장하는 것입니다. 조작부호를 만났을 때 창고 맨 위의 두 숫자는 조작부호에 대응하는 조작수입니다.가장 먼저 만나는 조작부호의 조작수는 반드시 삽입 표현식이 없기 때문에 값을 얻을 수 있다. 연산이 새로운 숫자를 얻은 후에 창고에 눌러서 다음 조작부호의 조작수로 삼을 수 있다.
내 코드: 숫자와 문자열을 변환할 때 비교적 못생겼다.
int evalRPN2(vector<string>& tokens)

    {

        if(tokens.size() == 1)

            return atoi(tokens[0].c_str());

        vector<string> nums;

        for(int i = 0; i < tokens.size(); i++)

        {

            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")

            {

                string sPreNum, sPostNum, sOp;

                int preNum, postNum, tmp;

                sPostNum = nums.back();

                nums.pop_back();

                sPreNum = nums.back();

                nums.pop_back();

                preNum = atoi(sPreNum.c_str());

                postNum = atoi(sPostNum.c_str());

                sOp = tokens[i];

                switch(sOp[0])

                {

                case '+':

                    tmp = preNum + postNum; break;

                case '-':

                    tmp = preNum - postNum; break;

                case '*':

                    tmp = preNum * postNum; break;

                case '/':

                    tmp = preNum / postNum; break;

                default:

                    break;

                }

                char ctmp[20];

                sprintf(ctmp, "%d", tmp);

                nums.push_back(ctmp);

            }

            else

            {

                nums.push_back(tokens[i]);

            }

        }

        return atoi(nums[0].c_str());

    }

 
대신은 귀착된 답안을 써서 상대적으로 짧지만 논리는 이해하기 어렵다.
int eval_expression(vector<string>& tokens, int& pt)

{

    string s = tokens[pt];



    if(s == "+" || s == "-" || s == "*" || s== "/") // tokens[r] is an operator

    {

        pt--;

        int v2 = eval_expression(tokens, pt);

        pt--;

        int v1 = eval_expression(tokens, pt);

        if(s == "+")

            return v1 + v2;

        else if(s == "-")

            return v1 - v2;

        else if(s == "*")

            return v1 * v2;

        else 

            return v1 / v2;

    }

    else // tokens[r] is a number

    {

        return atoi(s.c_str());

    }

}



int evalRPN(vector<string> &tokens) {

    int pt = tokens.size()-1; 

    return eval_expression(tokens, pt);

}

좋은 웹페이지 즐겨찾기