根據逆波蘭表示法，求表達式的值。

有效的運算符包括?+,?-,?*,?/?。每個運算對象可以是整數，也可以是另一個逆波蘭表達式。

說明：

整數除法只保留整數部分。
給定逆波蘭表達式總是有效的。換句話說，表達式總會得出有效數值且不存在除數為 0 的情況。
示例?1：

輸入: ["2", "1", "+", "3", "*"]
輸出: 9
解釋: ((2 + 1) * 3) = 9
示例?2：

輸入: ["4", "13", "5", "/", "+"]
輸出: 6
解釋: (4 + (13 / 5)) = 6
示例?3：

輸入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
輸出: 22
解釋:?
? ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

一道棧的題，

逆波蘭表示法對于基本的四則運算沒有優先級的限制，所以對于本題而言，運算符的優先順序完全是看運算符在tokens表達式內出現的先后順序來決定的。定義一個棧，一次遍歷tokens表達式，如果是數字則進棧，如果是運算符，則將棧stack內前兩個棧頂元素出棧，進行相應運算。

提交的代碼：

class Solution {
? ? public int evalRPN(String[] tokens) {
? ? ? ? ?int n = tokens.length;
?? ??? ? int i,j=0,sum,m,k;
?? ??? ? int[] nums = new int[n];
?? ??? ? for(i=0;i<n;i++)
?? ??? ? {
?? ??? ??? ? sum=0;
?? ??? ??? ? m = tokens[i].length();
?? ??? ??? ? if(tokens[i].charAt(0)>='0'&&tokens[i].charAt(0)<='9')
?? ??? ??? ? {
?? ??? ??? ??? ? for(k=0;k<m;k++)
?? ??? ??? ??? ? {
?? ??? ??? ??? ??? ? sum=sum*10+ (tokens[i].charAt(k)-'0');
?? ??? ??? ??? ? }
?? ??? ??? ??? ? nums[j++] = sum;
?? ??? ??? ? }
?? ??? ??? ? else if(tokens[i].charAt(0)=='-'&&m>1)
?? ??? ??? ? {
?? ??? ??? ??? ? for(k=1;k<m;k++)
?? ??? ??? ??? ? {
?? ??? ??? ??? ??? ? sum=sum*10+ (tokens[i].charAt(k)-'0');
?? ??? ??? ??? ? }
?? ??? ??? ??? ? nums[j++] = -sum;
?? ??? ??? ? }
?? ??? ??? ? else if(tokens[i].charAt(0)=='+')
?? ??? ??? ? {
?? ??? ??? ??? ? nums[j-2] = nums[j-2]+nums[j-1];
?? ??? ??? ??? ? j=j-1;
?? ??? ??? ? }
?? ??? ??? ? else if(tokens[i].charAt(0)=='-')
?? ??? ??? ? {
?? ??? ??? ??? ? nums[j-2] = nums[j-2]-nums[j-1];
?? ??? ??? ??? ? j=j-1;
?? ??? ??? ? }
?? ??? ??? ? else if(tokens[i].charAt(0)=='*')
?? ??? ??? ? {
?? ??? ??? ??? ? nums[j-2] = nums[j-2]*nums[j-1];
?? ??? ??? ??? ? j=j-1;
?? ??? ??? ? }
?? ??? ??? ? else if(tokens[i].charAt(0)=='/')
?? ??? ??? ? {
?? ??? ??? ??? ? nums[j-2] = nums[j-2]/nums[j-1];
?? ??? ??? ??? ? j=j-1;
?? ??? ??? ? }
?? ? ? ?}
?? ??? ? return nums[0];
? ? }
}

完整的代碼：

public class Solution150 {
?? ? public static int evalRPN(String[] tokens) {
?? ??? ? int n = tokens.length;
?? ??? ? int i,j=0,sum,m,k;
?? ??? ? int[] nums = new int[n];
?? ??? ? for(i=0;i<n;i++)
?? ??? ? {
?? ??? ??? ? sum=0;
?? ??? ??? ? m = tokens[i].length();
?? ??? ??? ? if(tokens[i].charAt(0)>='0'&&tokens[i].charAt(0)<='9')
?? ??? ??? ? {
?? ??? ??? ??? ? for(k=0;k<m;k++)
?? ??? ??? ??? ? {
?? ??? ??? ??? ??? ? sum=sum*10+ (tokens[i].charAt(k)-'0');
?? ??? ??? ??? ? }
?? ??? ??? ??? ? nums[j++] = sum;
?? ??? ??? ? }
?? ??? ??? ? else if(tokens[i].charAt(0)=='-'&&m>1)
?? ??? ??? ? {
?? ??? ??? ??? ? for(k=1;k<m;k++)
?? ??? ??? ??? ? {
?? ??? ??? ??? ??? ? sum=sum*10+ (tokens[i].charAt(k)-'0');
?? ??? ??? ??? ? }
?? ??? ??? ??? ? nums[j++] = -sum;
?? ??? ??? ? }
?? ??? ??? ? else if(tokens[i].charAt(0)=='+')
?? ??? ??? ? {
?? ??? ??? ??? ? nums[j-2] = nums[j-2]+nums[j-1];
?? ??? ??? ??? ? j=j-1;
?? ??? ??? ? }
?? ??? ??? ? else if(tokens[i].charAt(0)=='-')
?? ??? ??? ? {
?? ??? ??? ??? ? nums[j-2] = nums[j-2]-nums[j-1];
?? ??? ??? ??? ? j=j-1;
?? ??? ??? ? }
?? ??? ??? ? else if(tokens[i].charAt(0)=='*')
?? ??? ??? ? {
?? ??? ??? ??? ? nums[j-2] = nums[j-2]*nums[j-1];
?? ??? ??? ??? ? j=j-1;
?? ??? ??? ? }
?? ??? ??? ? else if(tokens[i].charAt(0)=='/')
?? ??? ??? ? {
?? ??? ??? ??? ? nums[j-2] = nums[j-2]/nums[j-1];
?? ??? ??? ??? ? j=j-1;
?? ??? ??? ? }
?? ? ? ?}
?? ??? ? return nums[0];
?? ? }
?? ? public static void main(String[] args)
?? ? {
?? ??? ? //String[] x = {"2", "1", "+", "3", "*"};
?? ??? ?// String[] x = {"4", "13", "5", "/", "+"};
?? ??? ? String[] x = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
?? ??? ? System.out.println(evalRPN(x));
?? ? }
}
?

總結

以上是生活随笔為你收集整理的Leetcode--150. 逆波兰表达式求值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。