后缀表达式-逆波兰表达式
我们平日里习惯用的表达式一般为中缀表达式，而对于计算机而言，中缀表达式是一种比较复杂的计算结构，相反逆波兰表达式对于计算机而言则显得比较简单，因为计算机普遍采用的内存结构为先进后出的栈式内存结构。
举例说明:
中缀表达式: 3+2*5-6
后缀表达式: 3 2 5 * + 6 -
java实现中缀表达式转后缀表达式
步骤:
- 新建栈stack,用于保存表达式,新建集合List<String>，用于保存最终的后缀表达式
- 将输入的中缀表达式表达式转换为List<String>集合
- 遍历中缀表达式集合
3.1 若为数字，直接放入最终的后缀表达式集合中
3.2 若为表达式，分情况处理
(1) 若表达式stack中为空或者表达式为"("，直接push进stack
(2) 若表达式为")",需要循环处理stack中的顶部元素,并依次将顶部元素非"()"放入最终的后缀表达式集合中,并将")"移除
(3) 若表达式的优先级低于stack中顶部元素的优先级(注意"()"没有优先级),需将stack顶部的表达式取出，放入最终的后缀表达式集合中,并将优先级低的表达式push进stack
(4) 若表达式的优先级高于或等于stack中顶部元素的优先级,直接push进stack
3.3 将stack中的表达式依次取出,添加进入最终的后缀表达式集合中
代码实现
import java.util.*;
/**
* 栈
* 实现逆波兰表达式算法，即后缀表达式
* 1、给定一个中缀表达式，例如 2+3*2+6
* 2、将中缀表达式转化为后缀表达式232*+6+ [2,3,2,*,+,6,+]
* 3、计算后缀表达式为14
*/
public class CalculateStack {
private static final List<String> EXPRESSION = Arrays.asList("+", "-", "*", "/", "(", ")");
private static final int ADD = 1;
private static final int SUBTRACT = 1;
private static final int MULTIPLY = 2;
private static final int DIVIDE = 2;
private static final Map<String, Integer> PRIORITY = new HashMap<>();
static {
PRIORITY.put("+", ADD);
PRIORITY.put("-", SUBTRACT);
PRIORITY.put("*", MULTIPLY);
PRIORITY.put("/", DIVIDE);
}
/**
* 中缀表达式转后缀表达式
* 步骤:
* 1.新建栈stack,用于保存表达式,新建集合List<String>，用于保存最终的后缀表达式结果
* 2.将输入的中缀表达式表达式转换为List<String>集合
* 3.遍历中缀表达式集合
* 3.1 若为数字，直接放入最终的后缀表达式集合中
* 3.2 若为表达式，分情况处理
* 3.2.1 若表达式stack中为空或者表达式为"("，直接push进stack
* 3.2.2 若表达式为")",需要循环处理stack中的顶部元素,并依次将顶部元素非"()"放入最终的后缀表达式集合中,并将")"移除
* 3.2.3 若表达式的优先级低于stack中顶部元素的优先级(注意"()"没有优先级),需将stack顶部的表达式取出，放入最终的后缀表达式集合中,并将优先级低的表达式push进stack
* 3.2.4 若表达式的优先级高于或等于stack中顶部元素的优先级,直接push进stack
* 3.3 将stack中的表达式依次取出,添加进入最终的后缀表达式集合中
*/
private static List<String> convertToSuffExper(String infixExpression){
Stack<String> exprStack = new Stack<>();
List<String> list = new ArrayList<>();
List<String> experList = convertExpToList(infixExpression);
for (int i =0; i < experList.size(); i ++){
String expression = experList.get(i);
if (isNumber(experList.get(i))){
list.add(experList.get(i));
}else {
if (exprStack.isEmpty() || "(".equals(expression) || ("(".equals(exprStack.peek()) && !")".equals(expression))){
exprStack.push(expression);
continue;
}
if ("(".equals(expression)){
exprStack.push(expression);
continue;
}
if (")".equals(expression)){
while (!"(".equals(exprStack.peek())){
list.add(exprStack.pop());
}
exprStack.pop();
continue;
}
if (PRIORITY.get(expression) < PRIORITY.get(exprStack.peek())){
list.add(exprStack.pop());
exprStack.push(expression);
}else {
exprStack.push(expression);
}
}
}
while (!exprStack.isEmpty()){
list.add(exprStack.pop());
}
System.out.println("转换成的后缀表达式为:" + list);
return list;
}
/**
* 将输入的中缀表达式表达式转换为List<String>集合
* @return
*/
private static List<String> convertExpToList(String infixExpression){
if (infixExpression == null || "".equals(infixExpression)){
throw new RuntimeException("输入的中缀表达式不能为空!");
}
infixExpression = infixExpression.replaceAll(" ", "");
List<String> result = new ArrayList<>();
for (int i =0; i < infixExpression.length(); i ++){
if (!charIsNumber(infixExpression.charAt(i))){
if (EXPRESSION.contains(infixExpression.charAt(i) + "")){
result.add(infixExpression.charAt(i) + "");
}else {
throw new RuntimeException("表达式 " +infixExpression.charAt(i) + "" + "非法!");
}
}else {
String str = "";
while (charIsNumber(infixExpression.charAt(i))){
str += infixExpression.charAt(i);
if (i < infixExpression.length() -1 && charIsNumber(infixExpression.charAt(i +1))){
i ++;
}else {
break;
}
}
result.add(str);
}
}
return result;
}
/**
* 计算后缀表达式
* @param suffixExpression 后缀表达式集合
*/
public static void calculateSuffix(List<String> suffixExpression){
Stack<String> numStack = new Stack<String>();//用于保存数字
for (String str : suffixExpression){
if (isNumber(str)){
numStack.push(str);
}else {
int num1 = Integer.parseInt(numStack.pop());
int num2 = Integer.parseInt(numStack.pop());
int result = caclulateRes(num1, num2, str);
numStack.push(result + "");
}
}
System.out.println("最终计算的结果为:" + numStack.pop());
}
private static int caclulateRes(int num1, int num2, String experssion){
int result;
switch (experssion){
case "+" :
result = num1 + num2;
break;
case "-" :
result = num2 - num1;
break;
case "*" :
result = num2 * num1;
break;
case "/" :
result = num2 / num1;
break;
default:
throw new RuntimeException("表达式" + experssion + "有误");
}
return result;
}
/**
* 判断是数字还是运算符
* @param
*/
private static boolean isNumber(String s){
return s.matches("^-?[1-9]\\d*$");//是否为整数数字
}
/**
* 判断是数字还是运算符
* @param
*/
private static boolean charIsNumber(char s){
return s >=48 && s <=57;//是否为整数数字
}
public static void main(String[] args) {
calculateSuffix(convertToSuffExper("(1+2)*((3*2))+6/2"));
}
}
测试:
输入中缀表达式 : (1+2) * ((3 * 2))+6/2
转换为后缀表达式为: 1, 2, +, 3, 2, *, *, 6, 2, /, +
计算结果为: 21
image.png
欢迎留言，我们一起成长~~
