ReversePolishNotation---后缀表达式（逆波兰表达式)
实现一个简易计算器(Basic Calculator)，计算简单表达式的值。
解题思路：
表达式求值可以分解为下列两步完成：
- 中缀表达式转为后缀表达式（逆波兰表达式）
- 后缀表达式求值
In order to parse and convert a given infix mathematical expression to RPN we will use the shunting-yard algorithm . Just like the evaluation of RPN, the algorithm is stack-based . For the conversion we will use two buffers (one for input, and one for output). Additionally we will use a stack for operators that haven’t been yet added to the output.
A simplified version of the Shunting-yard algorithm (complete version)
For all the input tokens [S1]:
Read the next token [S2];
If token is an operator (x) [S3]:
While there is an operator (y) at the top of the operators stack and either (x) is
left-associative and its precedence is less or equal to that of (y), or (x) is right-associative
and its precedence is less than (y) [S4]:
Pop (y) from the stack [S5];
Add (y) output buffer [S6];
Push (x) on the stack [S7];
Else If token is left parenthesis, then push it on the stack [S8];
Else If token is a right parenthesis [S9]:
Until the top token (from the stack) is left parenthesis, pop from the stack to the output buffer [S10];
Also pop the left parenthesis but don’t include it in the output buffer [S11];
Else add token to output buffer [S12].
While there are still operator tokens in the stack, pop them to output [S13]
Note: [SN] Relate with code.
Java实现：
public class ReversePolishNotation {
// Associativity constants for operators
private static final int LEFT_ASSOC = 0;
private static final int RIGHT_ASSOC = 1;
// Supported operators
private static final Map<String, int[]> OPERATORS = new HashMap<String, int[]>();
static {
// Map<"token", []{precendence, associativity}>
OPERATORS.put("+", new int[] { 0, LEFT_ASSOC });
OPERATORS.put("-", new int[] { 0, LEFT_ASSOC });
OPERATORS.put("*", new int[] { 5, LEFT_ASSOC });
OPERATORS.put("/", new int[] { 5, LEFT_ASSOC });
OPERATORS.put("%", new int[] { 5, LEFT_ASSOC });
OPERATORS.put("^", new int[] { 10, RIGHT_ASSOC });
}
/**
* Test if a certain token is an operator .
* @param token The token to be tested .
* @return True if token is an operator . Otherwise False .
*/
private static boolean isOperator(String token) {
return OPERATORS.containsKey(token);
}
/**
* Test the associativity of a certain operator token .
* @param token The token to be tested (needs to operator).
* @param type LEFT_ASSOC or RIGHT_ASSOC
* @return True if the tokenType equals the input parameter type .
*/
private static boolean isAssociative(String token, int type) {
if (!isOperator(token)) {
throw new IllegalArgumentException("Invalid token: " + token);
}
if (OPERATORS.get(token)[1] == type) {
return true;
}
return false;
}
/**
* Compare precendece of two operators.
* @param token1 The first operator .
* @param token2 The second operator .
* @return A negative number if token1 has a smaller precedence than token2,
* 0 if the precendences of the two tokens are equal, a positive number
* otherwise.
*/
private static final int cmpPrecedence(String token1, String token2) {
if (!isOperator(token1) || !isOperator(token2)) {
throw new IllegalArgumentException("Invalied tokens: " + token1
+ " " + token2);
}
return OPERATORS.get(token1)[0] - OPERATORS.get(token2)[0];
}
public static String[] infixToRPN(String[] inputTokens) {
ArrayList<String> out = new ArrayList<String>();
Stack<String> stack = new Stack<String>();
// For all the input tokens [S1] read the next token [S2]
for (String token : inputTokens) {
if (isOperator(token)) {
// If token is an operator (x) [S3]
while (!stack.empty() && isOperator(stack.peek())) {
// [S4]
if ((isAssociative(token, LEFT_ASSOC) && cmpPrecedence(
token, stack.peek()) <= 0)
|| (isAssociative(token, RIGHT_ASSOC) && cmpPrecedence(
token, stack.peek()) < 0)) {
out.add(stack.pop()); // [S5] [S6]
continue;
}
break;
}
// Push the new operator on the stack [S7]
stack.push(token);
} else if (token.equals("(")) {
stack.push(token); // [S8]
} else if (token.equals(")")) {
// [S9]
while (!stack.empty() && !stack.peek().equals("(")) {
out.add(stack.pop()); // [S10]
}
stack.pop(); // [S11]
} else {
out.add(token); // [S12]
}
}
while (!stack.empty()) {
out.add(stack.pop()); // [S13]
}
String[] output = new String[out.size()];
return out.toArray(output);
}
public static void main(String args[]) throws Exception {
ReversePolishNotation instance = new ReversePolishNotation();
String[] tokens = {"4", "13", "5", "/", "+"};
String[] input = "3 + 5 / 2 ".split(" ");//"( 1 + 2 ) * ( 3 / 4 ) ^ ( 5 + 6 )".split(" ");
String[] output = infixToRPN(input);
for (String token : output) {
System.out.print(token + " ");
}
System.out.println(instance.evalRPN(output));
}
public int evalRPN(String[] tokens) {//Reverse Polish Notation后缀表达式
int returnValue = 0;
String operators = "+-*/%^";
Stack<String> stack = new Stack<String>();
for(String t : tokens){
if(!operators.contains(t)){
stack.push(t);
}else{
int a = Integer.valueOf(stack.pop());
int b = Integer.valueOf(stack.pop());
int index = operators.indexOf(t);
switch(index){
case 0:
stack.push(String.valueOf(a+b));
break;
case 1:
stack.push(String.valueOf(b-a));
break;
case 2:
stack.push(String.valueOf(a*b));
break;
case 3:
stack.push(String.valueOf(b/a));
break;
case 4:
stack.push(String.valueOf(b%a));
break;
case 5:
stack.push(String.valueOf(b^a));
break;
}
}
}
returnValue = Integer.valueOf(stack.pop());
return returnValue;
}
}