代码实现如下:
package util;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class PolandExpression {
//计算方法
public int calculate (int num1,int num2,int ch){
int res = 0;
switch(ch){
case '+':
res = num1 + num2;
break;
case '-':
res = num2 - num1;
break;
case '*':
res = num1 * num2;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
return res;
}
//从左到右扫描,遇到数字,将数字压入堆栈,遇到运算符,弹出栈顶两个数,用运算符对它们做相应的计算,将结果入栈
public void afterExpression (String expression) {
List<String> list = parseMiddleToAfter(transferStringToMiddle(expression));
//用来存储符号和数据的栈
Stack<String> stack = new Stack<>();
//添加元素
for(String val : list){
//多位数的处理
if(val.matches("\\d+")){
stack.push(val);
}else{
if(isOper(val.charAt(0))){
int res;
//后操作数去处理前操作数
int num1 = Integer.parseInt(stack.pop());
int num2 = Integer.parseInt(stack.pop());
res = calculate(num1,num2,val.charAt(0));
stack.push(res+"");
}else{
throw new RuntimeException("wrong expression.");
}
}
}
System.out.printf("result = %d\n",Integer.parseInt(stack.pop()));
}
//将字符串转为中缀的List
public List<String> transferStringToMiddle (String target){
String normalStr = target.replaceAll("\\s+","");
List<String> list = new ArrayList<>();
String tempStr;
int index = 0;
do{
//判断是操作符还是数字 48-57是数字字符
if( normalStr.charAt(index) < 48 || normalStr.charAt(index) > 57){
list.add(""+ normalStr.charAt(index));
index++;
}else{
tempStr = "";
//如果连续字符进行拼串
while(index < normalStr.length() && normalStr.charAt(index) > 47 && normalStr.charAt(index) < 58){
tempStr += normalStr.charAt(index);
index++;
}
list.add(tempStr);
}
}while(index < normalStr.length());
return list;
}
//将中缀表达式转换为后缀表达式(波兰表达式)
public List<String> parseMiddleToAfter (List<String> list){
//符号栈
System.out.println("middleList:"+list);
Stack<String> s1 = new Stack<>();
//逆波兰结果集合
List<String> s2 = new ArrayList<>();
//遍历中缀集合
for(String item : list){
//数字直接入栈
//如果是“(”直接入栈,是“)”括号直接遍历直到遇到左括号为止,然后干掉左括号
if(item.matches("\\d+")){
s2.add(item);
}else if(item.equals("(")){
s1.push(item);
}else if(item.equals(")")){
while(!s1.peek().equals("(")){
s2.add(s1.pop());
}
s1.pop();
}else{
//操作符的比较:如果优先级比栈顶高,直接存入;否则将栈顶元素加入到s2中
//如果此操作符一直比栈中元素优先级低,要一直将栈顶元素弹出
// ( + )
while(s1.size() > 0 && priority(item) <= priority(s1.peek())){
s2.add(s1.pop());
}
s1.push(item);
}
}
//将栈中剩下的操作符都入集合
while(s1.size() > 0){
s2.add(s1.pop());
}
System.out.println("afterList:"+s2);
return s2;
}
//比较优先级
public int priority (String oper) {
int res = 0;
switch(oper){
case "+":
res = 1;
break;
case "-":
res = 1;
break;
case "*":
res = 2;
break;
case "/":
res = 2;
break;
default:
break;
}
return res;
}
//判断是否为操作符
public boolean isOper (char ch){
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
public static void main(String[] args) {
PolandExpression pe = new PolandExpression();
System.out.println("input the expression you want to caculate:");
Scanner input = new Scanner(System.in);
String expression = input.nextLine();
pe.afterExpression(expression);
//pe.afterExpression("(3 + 4)* 5+(6 +4)*4-8/ 2+10");
//( 3 + 4 )* 5 + ( 6 + 4 ) * 4 - 8 / 2 + 10 = 81
//( 4 + 5 ) * 3 - 14 / 2 = 20
}
}