字尾表達式相對于中綴表達式的優點：
1：不考慮運算優先級和括号。
2：從左到右單次掃描即可，時間複雜度O(1)。
注意：
堆棧是一種計算字尾表達式的理想資料結構，本例中筆者使用了java.util.Stack包，有必要一提的是，java中實作的Stack類由于是從java.util.Vector繼承而來，是以它包含了一些從父類繼承的方法，因為要凸顯棧式結構的實質，是以這裡筆者隻使用Push，Pop等一般堆棧共有的方法。
基本算法思路：
1：從左到右掃描表達式，依次識别對表達式中每個字元，判斷其為操作數還是操作符
2：如果是操作數，則将其壓入棧中
3：如果是操作符，則從棧頂彈出兩個元素，進行計算後将計算結果重新壓入棧中
4：重複上述過程，直至棧中隻剩餘一個元素，此時表達式也應該到達末尾
注意：為了簡化問題，上述過程并沒有對表達式是否合法進行判斷。
基本過程如圖：
代碼實作：
構造一個PostfixEvaluator類，基本屬性有
1：：+ - * / 四個char型字元常量
2：java.util.Stack,一個Integer型的堆棧
方法
1：public PostfixEvaluator()
重載構造函數，建立一個空棧
2：private boolean isOperator(String str)
用于判斷讀入字元是操作數還是操作符
3：private int calculateSingleOp(char operator, int num1, int num2)
根據從棧頂彈出的操作數和操作符計算單個表達式
4：public int evaluate (String str)
讀入操作數，壓入操作數
讀入操作符，彈出兩個操作數，并計算
壓入計算結果
package com.Stack.PostfixExpression;
import java.util.Stack;
import java.util.StringTokenizer;
/**
* Demonstrates the use of a stack to evaluate postfix expression
* @author Wang
*/
public class PostfixEvaluator {
/**
* constants for four calculative symbols
*/
private final char ADD = '+';
private final char SUBTRACT = '-';
private final char MULTIPLY = '*';
private final char DIVIDE = '/';
private Stack<Integer> stack;
/**
* Initialize with an empty stack<Integer>
*/
public PostfixEvaluator(){
stack = new Stack<Integer>();
}
/**
* Determines if the specified char is an operator
* @param str
* @return boolean is true if it is an operator
*/
private boolean isOperator(String str) {
return (str.equals("+") || str.equals("-") || str.equals("*") || str
.equals("/"));
}
/**
* Calculate
* @param operator
* @param num1
* @param num2
* @return the calculated result
*/
private int calculateSingleOp(char operator, int num1, int num2) {
int result = 0;
switch (operator)
{
case ADD:
result = num1 + num2;
break;
case SUBTRACT:
result = num1 - num2;
break;
case MULTIPLY:
result = num1 * num2;
break;
case DIVIDE:
result = num1 / num2;
break;
}
return result;
}
/**
* Evaluates the specified postfix expression
* if an operand is encountered, push it onto the stack.
* if an operator is encountered, pop two operand for operator to evaluate
* and push the calculated result onto the stack
* @param str String representation of a postfix expression
* @return integer value of the given expression
*/
public int evaluate (String str){
int num1, num2, result = 0;
// Temporary vase for every single char
String token = "";
StringTokenizer tokenizer = new StringTokenizer(str);
while (tokenizer.hasMoreTokens()){
// Tokenizer every single char from String
token = tokenizer.nextToken();
if (isOperator(token)){
// Transfer Integer object into int
num2 = (stack.pop()).intValue();
num1 = (stack.pop()).intValue();
result = calculateSingleOp(token.charAt(0), num1, num2);
// Push the calculated result onto the stack
stack.push(new Integer(result));
}
else
{
stack.push(new Integer(Integer.parseInt(token)));
}
}
return result;
}
}
測試代碼如下：
package com.Stack.PostfixExpression;
import java.util.Scanner;
public class Postfix {
public static void main(String[] args) {
String expression = "";
String again = "";
int result = 0;
try {
@SuppressWarnings("resource")
Scanner input = new Scanner(System.in);
do {
PostfixEvaluator evaluator = new PostfixEvaluator();
// Read in a valid postfix expression
System.out
.println("Please enter a valid postfix expression : ");
// Assignment
expression = input.nextLine();
result = evaluator.evaluate(expression);
System.out.println();
System.out
.println("After evaluating, the calculated result is : "
+ result);
// Again
System.out.println("Do you want to test again? [Y/N]");
again = input.nextLine();
System.out.println();
} while (again.equalsIgnoreCase("Y"));
}
catch (Exception IOException) {
System.out.println("Input exception reported.");
}
}
}
測試結果：
小結：棧式資料結構基本應用
新手上路，難免有不足之處，還請各位看官不吝指正。