给定一个逆波兰表达式,求表达式的值。
数据范围:表达式长度满足 ,表达式中仅包含数字和 + ,- , * , / ,其中数字的大小满足 。
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param tokens string字符串一维数组 * @return int整型 */ public int evalRPN (String[] tokens) { // write code here Stack<Integer> stack = new Stack<>(); for(int i = 0; i < tokens.length; i++) { if(isDigit(tokens[i])){ stack.push(Integer.parseInt(tokens[i])); }else{ if(tokens[i].equals("+")){ int num2 = stack.pop(); int num1 = stack.pop(); stack.push(num1 + num2); }else if(tokens[i].equals("-")){ int num2 = stack.pop(); int num1 = stack.pop(); stack.push(num1 - num2); }else if(tokens[i].equals("*")){ int num2 = stack.pop(); int num1 = stack.pop(); stack.push(num1 * num2); }else if(tokens[i].equals("/")){ int num2 = stack.pop(); int num1 = stack.pop(); stack.push(num1 / num2); } } } return stack.pop(); } private boolean isDigit(String s) { try{ Integer.parseInt(s); return true; }catch(Exception e) { return false; } } }
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])
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param tokens string字符串一维数组 * @return int整型 */ public int evalRPN (String[] tokens) { Stack<Integer> stack = new Stack<>(); for (String token : tokens) { if (token.equals("+")) { int b = stack.pop(); int a = stack.pop(); stack.push(a + b); } else if (token.equals("-")) { int b = stack.pop(); int a = stack.pop(); stack.push(a - b); } else if (token.equals("*")) { int b = stack.pop(); int a = stack.pop(); stack.push(a * b); } else if (token.equals("/")) { int b = stack.pop(); int a = stack.pop(); stack.push(a / b); } else { stack.push(Integer.parseInt(token)); } } return stack.pop(); } }
public int evalRPN (String[] tokens) { ArrayDeque<Integer> stack = new ArrayDeque<>(); for (String t : tokens) { if (t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/")) { int a = stack.pop(), b = stack.pop(); if (t.equals("+")) stack.push(b+a); else if (t.equals("-")) stack.push(b-a); else if (t.equals("*")) stack.push(b*a); else stack.push(b/a); } else { stack.push(Integer.parseInt(t)); } } return stack.peek(); }
#include<stdio.h> #include <stdlib.h> #include <string.h> struct node { char data; struct node* next; }; void NIBOLAN(char* p) { struct node* tail = malloc(sizeof(struct node)); tail->next = NULL; struct node* pre = NULL; int i = 0; while (*(p + i) != '\0') { if (*(p + i) >= 48 && *(p + i) <= 57) { struct node* pnew = malloc(sizeof(struct node)); pnew->data = *(p + i)-48; pnew->next = tail->next; tail->next = pnew; pre = tail->next->next; } else if (*(p + i) == '*' || *(p + i) == '/' || *(p + i) == '+' ||*(p + i) == '-') { if (*(p + i + 1) == '*' || *(p + i + 1) == '/' || *(p + i + 1) == '+' ||*(p + i + 1) == '-') { printf("error\n"); break; } else { struct node *k=tail->next; if (*(p + i) == '*') { pre->data=(tail->next->data)*(pre->data); tail->next=pre; k->next=NULL; free(k); } else if (*(p + i) == '/') { pre->data=(tail->next->data)/(pre->data); tail->next=pre; k->next=NULL; free(k); } else if (*(p + i) == '-') { pre->data=(tail->next->data)-(pre->data); tail->next=pre; k->next=NULL; free(k); } else if (*(p + i) == '+') { pre->data=(tail->next->data)+(pre->data); tail->next=pre; k->next=NULL; free(k); } else { printf("error\n"); break;//如果都不满足,在这就跳出了 } } } else { printf("error\n"); break; } i++; } //整个循环执行完,打印出最终结果 printf("%d",tail->next->data); } int main() { // char a[10];//只是给他分配了这么多的大小的空间,真实长度与用户输入有关 // struct node *t=init(); char a[10]; scanf("%s", a); char* p = a; NIBOLAN(p); }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param tokens string字符串一维数组 * @return int整型 */ public static int evalRPN(String[] tokens) { // write code here Deque<String> stack = new ArrayDeque<>(); for (String str : tokens) { if ("+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str)) { Integer optionNum2 = Integer.parseInt(stack.pop()); Integer optionNum1 = Integer.parseInt(stack.pop()); switch (str) { case "+": stack.push(String.valueOf(optionNum1 + optionNum2)); break; case "-": stack.push(String.valueOf(optionNum1 - optionNum2)); break; case "*": stack.push(String.valueOf(optionNum1 * optionNum2)); break; case "/": stack.push(String.valueOf(optionNum1 / optionNum2)); } } else { stack.push(str); } } return Integer.parseInt(stack.pop()); }
class Solution: def evalRPN(self , tokens: List[str]) -> int: #辅助栈 st = [] ma = ['+', '-', '*', '/'] # 遍历tokens for i, char in enumerate(tokens): if char not in ma: st.append(int(char)) elif (char in ma) and (len(st) >=2): operator = char result = eval("st[-2] {0} st[-1]".format(operator)) st.pop() st.pop() st.append(result) print(st) return int(st[-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(); } };
#include <cctype> #include <stack> #include <string> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param tokens string字符串vector * @return int整型 */ int priority(string s) { if(s=="$" ) return 0; else if(s=="+" || s=="-") return 1; else if(s=="*" || s=="/" ) return 2; else if(s=="#") return 3; else return -1; } bool Isdigit(string s) { if(s.size()>=1 && priority(s)==-1) return true; else return false; } int calc(int a,int b,string op) { if(op=="+") return a+b; else if(op=="-") return a-b; else if(op=="*") return a*b; else if(op=="/") return a/b; else return 0; } int evalRPN(vector<string>& tokens) { stack<string> num; stack<string> op; op.push("#"); for(int i=0;i<tokens.size();i++) { if(Isdigit(tokens[i])) num.push(tokens[i]); else { string opt=op.top(); if(priority(tokens[i])<priority(opt)) { int b=stoi(num.top()); num.pop(); int a=stoi(num.top()); num.pop(); num.push(to_string(calc(a,b,tokens[i]))); } else { op.push(tokens[i]); } }; } return stoi(num.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()
#include <string> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param tokens string字符串vector * @return int整型 */ int evalRPN(vector<string>& tokens) { // 用栈来辅助实现表达式的实现,只要是非运算符则转化为数字并保存起来。 // 遇到运算符则从栈里面拿出两个数字,按对应的运算符操作,清空栈并保存上一次的结果 // 运算符的下一个元素则继续转化为数字,再入栈,保持栈中有两个数字 // 若是最后遇到的是运算符则栈中只有一个元素,就是栈顶元素,返回即可 stack<int> Aux; int result = 0; int numbers = tokens.size(); for(int i = 0; i < numbers; i++){ if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"){ int temp = stoi(tokens[i]); // 转化为数字 Aux.push(temp); }else{ int temp = Aux.top(); // 提取数字1 Aux.pop(); if(tokens[i] == "+"){ result = Aux.top() + temp; // 提取数字2并运算 Aux.pop(); Aux.push(result); } else if (tokens[i] == "-") { result = Aux.top() - temp; Aux.pop(); Aux.push(result); } else if (tokens[i] == "*" ) { result = Aux.top() * temp; Aux.pop(); Aux.push(result); } else{ result = Aux.top() / temp; Aux.pop(); Aux.push(result); } } } return Aux.top(); } };