溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇“后綴表達式的java如何實現”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“后綴表達式的java如何實現”文章吧。
觀察一個普通的算式：3+4*5
我們當然知道，應該先計算 4*5 再將這個結果和3相加，就能得到最后的結果。
如果是一個復雜一些的算式：3+4*（（5-6）/7+8）
這依然難不倒我們，只要牢記（）的優先級最高，然后是*/，最后是+-就沒問題了，這就是通常的中綴表示法。
但是通過算法分析，這樣的表達式，由于每一次都需要判斷優先級，所以運行的時間應當是O（N^2）。
在表達式很長很復雜的時候，就需要一種更適合計算機的算法來計算了。
簡介
逆波蘭表示法（Reverse Polish notation，RPN，或逆波蘭記法），是一種是由波蘭數學家揚·武卡謝維奇1920年引入的數學表達式方式，在逆波蘭記法中，所有操作符置于操作數的后面，因此也被稱為后綴表示法。
逆波蘭記法不需要括號來標識操作符的優先級。逆波蘭記法中，操作符置于操作數的后面。
例如表達“三加四”時，寫作“3 4 +”，而不是“3 +4”。如果有多個操作符，操作符置于第二個操作數的后面，所以常規中綴記法的“3 - 4 + 5”在逆波蘭記法中寫作“3 4 - 5+”：先3減去4，再加上5。——維基百科逆波蘭表示法詞條。
這種表示法有以下特點：
不需要使用括號。和中綴表達式不同，逆波蘭表達式不需要遍歷整個算式來尋找一對括號。
逆波蘭表達式的實現一般基于堆棧。在計算機中，堆棧這種數據結構具有極快的效率。運行時間是O（N）。
不滿足交換律。
例如2*3+4*5
你可以這么計算，2 和 3 相乘的和是 5，把這個數存起來，再計算 4*5 的值，存起來， 最后在計算兩個存在一起的值。寫出來是這樣子的 2 3 * 4 5 * + 。這就是后綴或逆波蘭記法。
采用堆棧實現的過程很簡單，規則如下。
從頭開始讀取。讀取到如果是數字，則將其壓入棧中。如果是一個符號，就取兩次棧頂的元素通過該符號進行計算，再把得到的數壓入棧中。
Java實現
public class PRNCalculator {
public static double PRNCal(String PRN){
Stack<Double> stack = new Stack<Double>();
String[] ss = PRN.split(" ");
for(int i = 0; i < ss.length; i++){
if(ss[i].matches("\\d")) stack.push(Double.valueOf(ss[i]));
if(ss[i].matches("[+|-|*|/]")){
double b = stack.pop();
double a = stack.pop();
if(ss[i].equals("+")) stack.push(a + b);
if(ss[i].equals("-")) stack.push(a - b);
if(ss[i].equals("*")) stack.push(a * b);
if(ss[i].equals("/")) stack.push(a / b);
}
}
return stack.pop();
}
}Test類
public class PRNTest {
public static void main(String[] args) {
String s = "2 3 * 4 5 * + ";
double result = PRNCalculator.PRNCal(s);
System.out.println("輸入的逆波蘭表達式:" + s);
System.out.println("計算結果:" + result);
}
}打印結果：
輸入的逆波蘭表達式:2 3 * 4 5 * +
計算結果:26.0
和后綴表達式的計算方法類似，一個中綴記法轉換到后綴記法，也可以利用堆棧來實現。
從頭開始讀取。如果讀取到的是數字，將其輸出。如果讀取到的是符號，則判斷該符號的優先級是否高于棧頂或棧為空，是，則壓入棧中；否，則將棧頂輸出并繼續判斷。如果讀取到的是括號，”(“會直接被壓入棧；在讀取到”)”的時候，棧會一直彈出直到遇到”(“。下面是這個轉換的Java實現。
package PRNCalculator;
import java.util.Stack;
public class PRNCalculator {
public static String PRNTansf(String s){
Stack<String> stack = new Stack<String>();
String[] ss = s.split(" ");
StringBuffer sb = new StringBuffer();
for(int i = 0; i < ss.length; i++){
if(ss[i].matches("\\d")) sb.append(ss[i] + " ");
if(ss[i].matches("[+|-|*|/|(|)]")) {
if(stack.isEmpty()) {
stack.push(ss[i]);
} else {
if(ss[i].matches("[+|-]")) {
while(!stack.isEmpty() && !stack.peek().matches("[(]")) sb.append(stack.pop()).append(" ");
if(stack.isEmpty() || stack.peek().matches("[(]")) stack.push(ss[i]);
}
if(ss[i].matches("[*|/]")){
while(stack.peek().matches("[*|/]") && !stack.peek().matches("[(]")) sb.append(stack.pop()).append(" ");
if(stack.isEmpty() || stack.peek().matches("[(]") || stack.peek().matches("[+|-]")) stack.push(ss[i]);
}
if(ss[i].matches("[(]")) {
stack.push(ss[i]);
}
if(ss[i].matches("[)]")){
while(!stack.peek().matches("[(]")) sb.append(stack.pop()).append(" ");
if(stack.peek().matches("[(]")) stack.pop();
}
}
}
}
while(!stack.isEmpty()) sb.append(stack.pop()).append(" ");
return sb.toString();
}
}* Test類*
package PRNCalculator;
public class PRNTest {
public static void main(String[] args) {
String s = "4 + 5 + 8 * ( 6 + 8 * 7 ) / 3 + 4";
String PRN = PRNCalculator.PRNTansf(s);
System.out.println("輸入的表達式為：");
System.out.println(s);
System.out.println("輸出的逆波蘭表達式為：");
System.out.println(PRN);
double result = PRNCalculator.PRNCal(PRN);
System.out.println("該表達式計算結果為：");
System.out.println(result);
}
}打印結果：
輸入的表達式為：
4 + 5 + 8 * ( 6 + 8 * 7 ) / 3 + 4
輸出的逆波蘭表達式為：
4 5 + 8 6 8 7 * + * 3 / + 4 +
該表達式計算結果為：
178.33333333333334
從左至右掃描表達式
遇到數字時，將數字壓棧，遇到運算符時，彈出棧頂的兩個數，計算并將結果入棧
重復2直到表達式最右端，最后運算得出的值即為表達式的結果
計算后綴表達式的值：1 2 3 + 4 × + 5 -
從左至右掃描，將1，2，3壓入棧；
遇到+運算符，3和2彈出，計算2+3的值，得到5，將5壓入棧；
遇到4，將4壓入棧
遇到×運算符，彈出4和5，計算5×4的值，得到20，將20壓入棧；
遇到+運算符，彈出20和1，計算1+20的值，得到21，將21壓入棧；
遇到5，將5壓入棧；
遇到-運算符，彈出5和21，計算21-5的值，得到16為最終結果
public class ReversePolishNotation {
public static void main(String[] args) {
String notation = "10 2 3 + 4 * + 5 -";
ReversePolishNotation reversePN = new ReversePolishNotation();
Stack<Integer> numStack = new Stack<>();
//以空格分隔上述表達式，存到數組中
String[] s = notation.split(" ");
//遍歷數組
for (int i = 0; i < s.length; i++) {
if (!reversePN.isOperator(s[i])){
//如果不是運算符，則壓棧
numStack.push(Integer.parseInt(s[i]));
} else {
//為運算符，則取出棧頂的兩個數字進行運算
int result = reversePN.calculation(numStack.pop(), numStack.pop(), s[i]);
//將結果壓棧
numStack.push(result);
}
}
//循環結束，棧中僅剩的一個元素及為結果
System.out.println(numStack.pop());
}
//判斷是否是運算符
public boolean isOperator(String oper){
return oper.equals("+") ||oper.equals("-") ||oper.equals("*") ||oper.equals("/") ;
}
//計算
public int calculation(int num1, int num2, String oper){
switch (oper){
case "+":
return num2 + num1;
case "-":
return num2 - num1;
case "*":
return num2 * num1;
case "/":
return num2 / num1;
default:
return 0;
}
}
}以上就是關于“后綴表達式的java如何實現”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
