算法题:后缀表达式

    xiaoxiao2022-07-13  170

    题目描述

    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

    分析

    引用辅助堆栈,采用堆栈进行将int和运算符分别压栈存储

    代码

    class Solution { public: int evalRPN(vector<string> &tokens) { //建立int数字堆栈 stack<int>Stk; int a = 0,b=0,c=0; for(auto temp:tokens) { //判断是否为字符 if(temp == "+"||temp == "-"||temp=="*"||temp == "/") { //int堆栈存储数小于2 if(Stk.size()<2) return 0; a = Stk.top();Stk.pop(); b = Stk.top();Stk.pop(); switch(transform(temp)) { case '+':c = a + b;break; case '-':c = b - a;break; case '*':c = b * a;break; case '/':c = b / a;break; } Stk.push(c); } //如果为数字,压栈 else { Stk.push(atoi(temp.c_str())); } } return Stk.top(); } private: //字符串hash到字符 char transform(string s){ char temp; if(s=="+") temp = '+'; else if(s=="-") temp = '-'; else if(s=="*") temp = '*'; else if(s=="/") temp = '/'; return temp; } };

    总结

    合理引用辅助内存,栈。 stack是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶。

    最新回复(0)