原则:数字输出,运算符进栈,括号匹配出栈,栈顶优先级低不出栈
public class postfix {
public static String[] outPostfix(String[] infix){
String[] postfix = new String[100];
int index = 0;
int bracket = 0; //标记括号的对数
Map operatorMap = new HashMap<>(); // 用hashmap存储每个运算符的优先度
operatorMap.put("+", 1);
operatorMap.put("-", 1);
operatorMap.put("*", 2);
operatorMap.put("/", 2);
Stack<String> postfixStack = new Stack<>(); //用于存储后缀算法的运算符
for (int i = 0; i < infix.length && infix[i] != null; i++) {
String current = infix[i];
if (current.charAt(0) >= '0' && current.charAt(0) <= '9'){ //遇到数字直接放入后缀数组
postfix[index++] = current;
}else {
if (postfixStack.isEmpty()){ //保证后缀运算符栈不为空
postfixStack.push(current);
}
/* *
*如果括号已经全部处理,而且当前字符不是括号,
*后缀运算符栈顶不是括号,并且栈顶运算符优先度小于当前运算符优先度,
*将当前遍历运算符后边的数字放入后缀数组中,再将当前运算符放入后缀数组中。
*/
else if (bracket == 0 && !isBracket(current) &&
!isBracket(postfixStack.peek()) &&
Integer.parseInt(String.valueOf(operatorMap.get(postfixStack.peek()))) < Integer.parseInt(String.valueOf(operatorMap.get(current)))){
postfix[index++] = infix[i + 1];
postfix[index++] = infix[i];
i++;
}
/**
* 同理 栈顶运算符优先度大于等于当前运算符优先度,
*将栈顶运算符放入后缀数组中,再将当前遍历的运算符放入栈中
*/
else if (bracket == 0 && !isBracket(current) &&
!isBracket(postfixStack.peek()) &&
Integer.parseInt(String.valueOf(operatorMap.get(postfixStack.peek()))) >= Integer.parseInt(String.valueOf(operatorMap.get(current)))){
postfix[index++] = postfixStack.pop();
postfixStack.push(current);
}
else {
if (current.equals("(")) bracket++; // 若遇到左括号,bracket加1
postfixStack.push(current);
if (postfixStack.peek().equals(")")){ //遇到右括号,bracket减1,同时将栈中括号间的运算符出栈
bracket--;
postfixStack.pop();
while (!postfixStack.peek().equals("(")){
postfix[index++] = postfixStack.pop();
}
postfixStack.pop();
}
}
}
}
while (!postfixStack.isEmpty()) postfix[index++] = postfixStack.pop();
return postfix;
}
public static double result(String[] postfix){
double result = 0;
Stack<Double> computeStack = new Stack();
for (int i = 0; i < postfix.length && postfix[i] != null; i++) {
String current = postfix[i];
//当前字符为数字,则入栈
if (current.charAt(0) >= '0' && current.charAt(0) <= '9'){
computeStack.push(todouble(current));
}
//当前字符为运算符,从栈顶取出两个数字运算出结果,并放入栈中
else {
switch (current){
case "+": result = computeStack.pop() + computeStack.pop();
computeStack.push(result);break;
case "-": result = -(computeStack.pop() - computeStack.pop());
computeStack.push(result);break;
case "*": result = computeStack.pop() * computeStack.pop();
computeStack.push(result);break;
case "/": result = 1 / (computeStack.pop() / computeStack.pop());
computeStack.push(result);break;
default: break;
}
}
}
return result;
}
public static double todouble(String str){
double num = 0;
num = Double.valueOf(Integer.parseInt(str));
return num;
}
public static boolean isBracket(String str){
if (str.equals("(") || str.equals(")")) return true;
else return false;
}
public static void main(String[] args){
String[] infix = new String[]{"9", "+", "(", "3", "-", "1", ")", "*", "3", "+", "10", "/", "2"};
String[] infix1 = new String[100];
int i = 0;
Scanner in=new Scanner(System.in);
while (in.hasNext()){
infix1[i++] = in.nextLine();
}
in.close();
infix = outPostfix(infix1);
for (i = 0; i < infix.length && infix[i] != null; i++) {
System.out.print(infix[i] + " ");
}
System.out.print("\n");
System.out.println(result(infix));
}
}
输入:
2
*
(
3
+
3
*
(
5
+
4
)
)
后缀表达式:
2 3 3 5 4 + * + *
结果:60.0