将一个算术表达式转化成为逆波兰式的一个例子

//将一个算术表达式转化成为逆波兰式
package com.snow.ee;
 
import java.util.Stack;
 
public class TestNibolanshi {
String expression ="(1*5-12*(3+5))/7+5";
public static void main(String[] args) {
TestNibolanshi test= new TestNibolanshi();
test.nibolanshi();
}
//判断是否为数字
public static boolean isDigit(char c){
if(c>=‘0‘&&c<=‘9‘){
return true;
}
return false;
}
//判断是否是操作符
public static boolean isOperator(char c){
if(c==‘+‘||c==‘-‘||c==‘*‘||c==‘/‘||c==‘(‘||c==‘)‘){
return true;
}        
return false;
}
//计算
public static double simpleCal(double leftNum, char c, double rightNum) { 
        switch (c) { 
        case ‘+‘: 
            return leftNum + rightNum; 
        case ‘-‘: 
            return leftNum - rightNum; 
        case ‘*‘: 
            return leftNum * rightNum; 
        case ‘/‘: 
            return leftNum / rightNum; 
        default: 
            throw new RuntimeException(); 
        } 
    }
//优先级比较： 1表示>,0表示=,-1表示<,9表示无法比较
//优先级高的先计算
char [] c          =                          {‘+‘,‘-‘,‘*‘,‘/‘,‘(‘,‘)‘,‘#‘};
int[][] youxianji={    /* + */    { 1,  1, -1, -1, -1,  1,  1},
                                    /* - */     { 1,  1, -1, -1, -1,  1,  1},        
                                    /* * */    { 1,  1,  1,  1, -1,  1,  1}, 
                                   /* / */     { 1,  1,  1,  1, -1,  1,  1}, 
                                   /* ( */      {-1, -1, -1, -1, -1,  0,  9},
                                   /* ) */      { 1,  1,  1,  1,  9,  1,  1},
                                   /* # */     {-1, -1, -1, -1, -1,  9,  0}
};
//假设计算的数据都为整数int
public int youxianji(char c1,char c2){
int m = 0,n = 0;
for(int i=0;i<c.length;i++){
if(c[i]==c1){
m=i;
break;
}
}
for(int i=0;i<c.length;i++){
if(c[i]==c2){
n=i;
break;
}
}
return youxianji[m][n];
}
//将一个表达式变为逆波兰式
public void nibolanshi(){
Stack<String> result = new Stack<>();//结果
Stack<Character> operator = new Stack<>();//存放运算符
operator.push(‘#‘);
 
char[] arr  = expression.toCharArray();
int arrlen = 0;//表示目前扫描到arr数组的第arrlen个
StringBuffer tempVar = new StringBuffer();//存放临时变量
 
while(arrlen<arr.length){
if(Test01.isDigit(arr[arrlen])){//1、若arr[arrlen]为操作数，则分析出完整的操作数，然后压入result栈顶
do{
tempVar.append(arr[arrlen]);
arrlen++;
}while(arrlen<arr.length && Test01.isDigit(arr[arrlen]));//此处应先判断arrlen<arr.length
 
result.push(tempVar.toString());
tempVar.setLength(0);
} else if(arrlen<arr.length && Test01.isOperator(arr[arrlen]) ){//2、若arr[arrlen]为操作符:
// 1表示>,0表示=,-1表示<,9表示无法比较;
//如果 < 即yxj=-1,直接放到operator中
//如果 > j即yxj=1,将operator的栈顶元素放入result 中，直到 yxj=-1
int yxj = this.youxianji(operator.peek(), arr[arrlen]);//计算操作符优先级
if(yxj==-1){ //若operator 栈的栈顶操作符的优先级 > arr[arrlen] 的优先级，直接压入operator栈
operator.push(arr[arrlen]);
}else if(yxj==1){//若operator操作符栈顶元素的符号的优先级 > arr[arrlen]时：
do{  //先将operator栈中所有优先级 > arr[arrlen]的操作符压入result栈，
 //直到operator栈顶元素优先级 < 或 = arr[arrlen]
result.push(operator.pop().toString());                                                        
}while(youxianji(operator.peek(), arr[arrlen])==1);
//然后判断operator栈顶操作符优先级到底是< 还是 = arr[arrlen]
//若 < 直接压入operator栈顶
if(youxianji(operator.peek(), arr[arrlen])==-1){
operator.push(arr[arrlen]);
} else if(youxianji(operator.peek(), arr[arrlen])==0){//若 = 将operator 栈顶操作符去除
operator.pop();
}
}else if(yxj==0){//3、若operator操作符栈顶元素的符号的优先级 = arr[arrlen]时：
//直接将operator 栈顶操作符去除
operator.pop();
}
//然后判断下一个操作符
arrlen++;
}
}
 
while(!operator.isEmpty() && operator.peek()!=‘#‘){
result.push(operator.pop().toString());
}
 
for(String s:result){
System.out.print(s+" ");
}
}
}
//注意：转换为逆波兰式的算法的关键在于比较操作符之间的优先级