逆波兰表达式求值

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串vector 
     * @return int整型
     */
    int evalRPN(vector<string>& tokens) {
        // write code here
        // 时间复杂度O(N)，空间复杂度O(N)
        stack<string> stk;
        int n1, n2, res;
        for (string &s : tokens) {
            if (s == "+" || s == "-" || s == "*" || s == "/") {
                n2 = stoi(stk.top());
                stk.pop();
                n1 = stoi(stk.top());
                stk.pop();
                if (s == "+") res = n1 + n2;
                else if (s == "-") res = n1 - n2;
                else if (s == "*") res = n1 * n2;
                else res = n1 / n2;
                stk.push(to_string(res));
            } else stk.push(s);
        }
        return stoi(stk.top());
    }
};

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param tokens string字符串一维数组 
# @return int整型
#
class Solution:
    def evalRPN(self , tokens: List[str]) -> int:
        # write code here
        """
            逆波兰表达式
                1. 维护一个栈，栈中只保存数值 -> stack = []
                2. 如果遇到数，存到栈中
                3. 如果遇到运算符，从stack中取出两个元素进行相应的计算并存储回栈中
        """

        stack = []

        for elem in tokens:
            # 如果是运算符
            if elem in "+-*/":
                # 从栈中取出两个元素
                first = stack.pop()
                second = stack.pop()

                # 根据运算符进行对应计算
                if elem == "+":
                    stack.append(second + first)
                elif elem == "-":
                    stack.append(second - first)
                elif elem == "*":
                    stack.append(second * first)
                else:
                    stack.append(int(second / first))
                
            # 如果数
            else:
                stack.append(int(elem))

        # 最后取出栈的元素
        return stack.pop()

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串vector 
     * @return int整型
     */
    int evalRPN(vector<string>& tokens) {
        // write code here
        stack<int> sta;
        for(int i=0;i<tokens.size();i++)
        {
            if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/")
            {
            int num=sta.top();sta.pop();int num1=sta.top();sta.pop();
                
            if(tokens[i]=="+"){sta.push(num+num1);}
            if(tokens[i]=="-"){sta.push(num1-num);}
            if(tokens[i]=="*"){sta.push(num*num1);}
            if(tokens[i]=="/"){sta.push(num1/num);}
            }
            else {sta.push(stoi(tokens[i]));}
        }
        return sta.top();
        
    }
};

class Solution:
    def evalRPN(self , tokens: List[str]) -> int:
        # write code here
        ls = []
        for i in range(len(tokens)):
            if tokens[i] in ["+","-","*","/"]:
                l1 = ls.pop()
                l2 = ls.pop()
                res = str(int(eval(l2 + tokens[i] + l1)))
                ls.append(res)
            else:
                ls.append(tokens[i])
        return int(ls[-1])

int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for (auto &s: tokens) {
        if (s=="+"|| s=="-"||s=="*"||s=="/") {
            auto b = st.top();
            st.pop();
            auto a = st.top();
            st.pop();
            switch (s[0]) {
                case '+':
                    st.push(a+b);
                    break;
                case '-':
                    st.push(a-b);
                    break;
                case '*':
                    st.push(a*b);
                    break;
                case '/':
                    st.push(a/b);
                    break;
            }
        }
        else st.push(stoi(s));
    }
    return st.top();
}

//先出栈的是右操作数，后出栈的是左操作数
typedef struct lnode {
    int data;
    struct lnode* next;
} node, *stack;

void Push(stack* p, int a) {
    stack cur = (stack)malloc(sizeof(node));
    if (cur == NULL) return;
    cur->data = a;
    cur->next = *p;
    *p = cur;
}
void Pop(stack* p) {
    if (*p != NULL) *p = (*p)->next;
}

int Add(int x, int y) {
    return x + y;
}
int Sub(int x, int y) {
    return x - y;
}
int Mul(int x, int y) {
    return x * y;
}
int Div(int x, int y) {
    return x / y;
}
int Signal(char* s) {
    if (strcmp(s, "+") == 0) return 1;
    else if (strcmp(s, "-") == 0) return 2;
    else if (strcmp(s, "*") == 0) return 3;
    else if (strcmp(s, "/") == 0) return 4;
    else return 0;
}

int evalRPN(char** tokens, int tokensLen ) {
    // write code here
    int j = 0;
    stack s = NULL;
    int(*cal[5])(int, int) = {0, Add, Sub, Mul, Div};
    for (int i = 0; i < tokensLen; i++) {
        char* str =
            tokens[i];//在使用（*tokens）+i赋值变量时程序结果错误
        j = Signal(str);
        if (j) {//遇到运算符出栈运算并将结果入栈
            int right = s->data;
            Pop(&s);
            int left = s->data;
            Pop(&s);
            int z = (*cal[j])(left, right);//使用了函数指针数组
            Push(&s, z);
        } else {//非运算符，将字符串转换成整形入栈
            int m = atoi(str);
            Push(&s, m);
        }
    }
    return s->data;
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串一维数组 
     * @return int整型
     */
    public int evalRPN (String[] tokens) {
        // write code here
        Stack<Integer> st = new Stack<>();
        for(int i = 0;i < tokens.length;i++){
            if(tokens[i].equals("+")){
                int second = st.pop();
                int first = st.pop();
                st.push(first + second);
            }else if(tokens[i].equals("-")){
                int second = st.pop();
                int first = st.pop();
                st.push(first - second);
            }else if(tokens[i].equals("*")){
                int second = st.pop();
                int first = st.pop();
                st.push(first * second);
            }else if(tokens[i].equals("/")){
                int second = st.pop();
                int first = st.pop();
                st.push(first / second);
            }else{
                st.push(Integer.parseInt(tokens[i]));
            }
        }
        return st.pop();
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param tokens string字符串vector 
     * @return int整型
     */
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for(int i=0; i<tokens.size(); i++){

            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "/" || tokens[i] == "*") {
                int a = s.top();
                s.pop();

                int b = s.top();
                s.pop();

                if(tokens[i] == "+")
                    s.push(a + b);
                else if(tokens[i] == "-")
                    s.push(b - a);
                else if(tokens[i] == "*")
                    s.push(a * b);
                else if(tokens[i] == "/")
                    s.push(b / a);
            }
            else
                s.push(stoi(tokens[i])); //stoi函数是将字符串转换为整数的函数。
               //全称是string to integer。可处理带有正负号的10进制数字字符串,将其转换为相应的整数类型
        }
        return s.top();
    }
};

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param tokens string字符串一维数组 
# @return int整型
#
class Solution:
    def evalRPN(self , tokens: List[str]) -> int:
        # write code here
        s=[]

        for char in tokens:
            if char in "+ -  *  /" :
                b=s.pop()
                a=s.pop()
                if char=='+':
                    c=a+b
                elif char=='-':
                    c=a-b
                elif char=='*':
                    c=a*b
                elif char=='/':
                    c=int(a/b)
                s.append(c)
            else:
                s.append(int(char))
        return s.pop()