具体步骤如下:
1)初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2)从左至右扫描中缀表达式；
3)遇到操作数时，将其压s2；
4)遇到运算符时，比较其与s1栈顶运算符的优先级：
(1)如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
(2)否则，若优先级比栈顶运算符的高，也将运算符压入s1；
(3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较;
5)遇到括号时：
(1) 如果是左括号“(”，则直接压入s1
(2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6)重复步骤2至5，直到表达式的最右边
7)将s1中剩余的运算符依次弹出并压入s2
8)依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下
| 扫描到的元素 |
s2(栈底->栈顶) |
s1 (栈底->栈顶) |
说明 |
| 1 |
1 |
空 |
数字，直接入栈 |
| + |
1 |
+ |
s1为空，运算符直接入栈 |
| ( |
1 |
+ ( |
左括号，直接入栈 |
| ( |
1 |
+ ( ( |
同上 |
| 2 |
1 2 |
+ ( ( |
数字 |
| + |
1 2 |
+ ( ( + |
s1栈顶为左括号，运算符直接入栈 |
| 3 |
1 2 3 |
+ ( ( + |
数字 |
| ) |
1 2 3 + |
+ ( |
右括号，弹出运算符直至遇到左括号 |
| × |
1 2 3 + |
+ ( × |
s1栈顶为左括号，运算符直接入栈 |
| 4 |
1 2 3 + 4 |
+ ( × |
数字 |
| ) |
1 2 3 + 4 × |
+ |
右括号，弹出运算符直至遇到左括号 |
| - |
1 2 3 + 4 × + |
- |
-与+优先级相同，因此弹出+，再压入- |
| 5 |
1 2 3 + 4 × + 5 |
- |
数字 |
| 到达最右端 |
1 2 3 + 4 × + 5 - |
空 |
s1中剩余的运算符 |
结果为 "1 2 3 + 4 × + 5 –"
package com.wang;
import java.util.*;
public class Test {
public static void main(String[] args) {
//中缀表达式
String exp="1+((2+3)*4)-5";
List<String> inlist=toExp(exp);
System.out.println("中缀表达式: "+inlist);
//对应的后缀表达式
List<String> parseList = parseList(inlist);
System.out.println("对应的后缀表达式: "+parseList);
/*String Poland="3 4 + 5 * 6 -";
//先将表达式存入Arralist，遍历Arralist配合栈完成计算
List<String> getlist = getlist(Poland);
System.out.println(getlist);*/
int res=compute(parseList);
System.out.println("结果: "+res);
}
public static List<String> getlist(String Poland) {
//按空格分割字符串并存入数组
String[] split = Poland.split(" ");
ArrayList<String> arrayList = new ArrayList<String>();
//遍历数组存入集合
for (String i :split) {
arrayList.add(i);
}
return arrayList;
}
public static int compute(List<String> list) {
Stack<String> stack=new Stack<String>();
for (String i : list) {
//使用正则表达式取出多位数字
if (i.matches("\\d+")) {
//入栈
stack.push(i);
}else {
//取出两个运算后入栈
int num2=Integer.parseInt(stack.pop());
int num1=Integer.parseInt(stack.pop());
int res=0;
if(i.equals("+")) {
res=num1+num2;
}else if (i.equals("-")) {
res=num1-num2;
}else if (i.equals("*")) {
res=num1*num2;
}
else if (i.equals("/")) {
res=num1/num2;
}
stack.push(res+"");
}
}
return Integer.parseInt(stack.pop());
}
//将中缀表达式存入集合 也就是转成1,+,(,(,2,+,3,),*,4,),-,5
public static List<String> toExp(String s){
ArrayList<String> ls = new ArrayList<String>();
//用于遍历中缀字符串
int i=0;
//用于拼接多位数
String str;
//每遍历一位就放进c里
char c;
do {
//如果它是一个字符就加入ls
if((c=s.charAt(i))<48||(c=s.charAt(i))>59) {
ls.add(""+c);
i++;
}else {
//如果是一个数，则需要考虑是否多位数
//每次拼接前重置str
str="";
while (i<s.length()&&(c=s.charAt(i))>=48&&(c=s.charAt(i))<=59) {
str+=c;
i++;
}
ls.add(str);
}
} while (i<s.length());
return ls;
}
//将得到的中缀表达式分成两部分
//存入符号栈和中间结果栈
public static List<String> parseList(List<String> ls){
//符号栈
Stack<String> s1 = new Stack<String>();
//中间结果栈
ArrayList<String> s2 = new ArrayList<String>();
for (String s : ls) {
//如果是一个数就加入ls1
if (s.matches("\\d+")) {
s2.add(s);
}else if (s.equals("(")) {
s1.push(s);
}else if (s.equals(")")) {
//如果是右括号则依次弹出s1栈顶的运算符，压入s2，直到遇到左括号为止
while (!s1.peek().equals("(")) {
s2.add(s1.pop());
}
//将括号弹出消除
s1.pop();
}else {
while(s1.size()!=0&&Oper.getv(s1.peek())>=Oper.getv(s)) {
s2.add(s1.pop());
}
s1.push(s);
}
}
//将s1中剩余的运算符依次弹出并加入s2
while(s1.size() != 0 ) {
s2.add(s1.pop());
}
return s2;
}
}
class Oper{
private static int ADD=1;
private static int SUB=1;
private static int MUL=1;
private static int DIV=1;
public static int getv(String oper) {
int su=0;
switch (oper) {
case "+":
su=ADD;
break;
case "-":
su=SUB;
break;
case "*":
su=MUL;
break;
case "/":
su=DIV;
break;
}
return su;
}
}