思路逆波兰表达式后缀表达式的特点是运算符在操作数之后且不需要括号。用栈求解最自然· 遇到数字入栈· 遇到运算符弹出栈顶两个元素做运算把结果压回栈遍历结束后栈里剩下的唯一元素就是答案。代码classSolution{publicintevalRPN(String[]tokens){DequeIntegerstacknewArrayDeque();for(Stringt:tokens){switch(t){case-stack.push(stack.pop()stack.pop());case*-stack.push(stack.pop()*stack.pop());case--{intbstack.pop();intastack.pop();stack.push(a-b);}case/-{intbstack.pop();intastack.pop();stack.push(a/b);}default-stack.push(Integer.parseInt(t));}}returnstack.pop();}}用数组手动模拟栈更快避免装箱classSolution{publicintevalRPN(String[]tokens){int[]stacknewint[tokens.length];inttop-1;for(Stringt:tokens){switch(t){case-stack[--top]stack[top1];// 等价写法见下方说明case--{intbstack[top--];stack[top]-b;}case*-{intbstack[top--];stack[top]*b;}case/-{intbstack[top--];stack[top]/b;}default-stack[top]Integer.parseInt(t);}}returnstack[top];}}如果觉得上面 的写法绕可以直接用最直白的版本intbstack[top--];intastack[top--];stack[top]ab;关键点减法/除法有顺序栈顶是右操作数 b次栈顶是左操作数 a必须算 a - b、a / b写反会得到错误答案或被 0 除。除法向零截断题目要求 6 / -132 0Java 的整数 / 本身就是向零截断直接使用即可不需要额外处理。Java 求值顺序stack.pop() stack.pop() 中 Java 保证从左到右求值先弹出的是右操作数加减乘除这里恰好可交换对 、* 无影响但为可读性建议还是显式写。示例走一遍tokens [“2”,“1”,“”,“3”,“*”]token 操作 栈底→顶2 入栈 [2]1 入栈 [2, 1]123 [3]3 入栈 [3, 3]3*39 [9]结果 9即 (21)*3。复杂度· 时间O(n)每个 token 处理一次· 空间O(n)栈最多存 n 个元素易错点· 忘记负数“-11” 用 Integer.parseInt 能正确解析不要自己手动按字符判断符号。· 用 switch 判断字符串时不要用 这里的 switch 用的是 equals 语义是安全的。
思路逆波兰表达式后缀表达式的特点是运算符在操作数之后且不需要括号。用栈求解最自然· 遇到数字入栈· 遇到运算符弹出栈顶两个元素做运算把结果压回栈遍历结束后栈里剩下的唯一元素就是答案。代码classSolution{publicintevalRPN(String[]tokens){DequeIntegerstacknewArrayDeque();for(Stringt:tokens){switch(t){case-stack.push(stack.pop()stack.pop());case*-stack.push(stack.pop()*stack.pop());case--{intbstack.pop();intastack.pop();stack.push(a-b);}case/-{intbstack.pop();intastack.pop();stack.push(a/b);}default-stack.push(Integer.parseInt(t));}}returnstack.pop();}}用数组手动模拟栈更快避免装箱classSolution{publicintevalRPN(String[]tokens){int[]stacknewint[tokens.length];inttop-1;for(Stringt:tokens){switch(t){case-stack[--top]stack[top1];// 等价写法见下方说明case--{intbstack[top--];stack[top]-b;}case*-{intbstack[top--];stack[top]*b;}case/-{intbstack[top--];stack[top]/b;}default-stack[top]Integer.parseInt(t);}}returnstack[top];}}如果觉得上面 的写法绕可以直接用最直白的版本intbstack[top--];intastack[top--];stack[top]ab;关键点减法/除法有顺序栈顶是右操作数 b次栈顶是左操作数 a必须算 a - b、a / b写反会得到错误答案或被 0 除。除法向零截断题目要求 6 / -132 0Java 的整数 / 本身就是向零截断直接使用即可不需要额外处理。Java 求值顺序stack.pop() stack.pop() 中 Java 保证从左到右求值先弹出的是右操作数加减乘除这里恰好可交换对 、* 无影响但为可读性建议还是显式写。示例走一遍tokens [“2”,“1”,“”,“3”,“*”]token 操作 栈底→顶2 入栈 [2]1 入栈 [2, 1]123 [3]3 入栈 [3, 3]3*39 [9]结果 9即 (21)*3。复杂度· 时间O(n)每个 token 处理一次· 空间O(n)栈最多存 n 个元素易错点· 忘记负数“-11” 用 Integer.parseInt 能正确解析不要自己手动按字符判断符号。· 用 switch 判断字符串时不要用 这里的 switch 用的是 equals 语义是安全的。
