飞行日记之数据结构与算法分析——栈与四则运算(2)
飞行日记之数据结构与算法分析——栈与四则运算(2)
本次重点讲解利用后缀表达式完成四则运算操作中,具体如何将我们熟悉的中缀表达式转换成后缀表达式的形式,便于计算机的理解和计算。
中缀表达式怎么转成后缀表达式?
思路与步骤:
-
1)初始化两个栈,分别用于存储后缀表达式结果S1和利用S2栈完成运算符号的指定位置输出; -
2)从左往右扫描中缀表达式,当扫描到数字时,直接压入到S1栈中; -
3)当扫描到运算符号时(不包括括号):
case1: 如果S1栈为空或者栈顶符号为“(”时,直接将扫描的运算符号压入到栈S1中;
case2: 如果不是case1情况,比较扫描到的符号与S1栈顶符号的优先级,如果优先级高于栈顶符号,则直接压入栈S1;否则,弹出S1栈顶符号并压入S2栈中,返回地 3)继续与S1栈顶符号比较;
-
4)当扫描到括号时(包括左右括号):
case1:如果是左括号“(”,则直接压入栈S1中;
case2:如果是右括号“)”,则依次弹出栈S1栈顶符号并压入S2栈中,直至S1栈顶元素为左括号“(”,弹出栈顶符号(即左括号)丢弃;
-
5)重复2)3)4)步骤,直至扫描到中缀表达式最后一位,将栈S1中所有符号弹出并依次压入到S2栈中; -
6)依次弹出S2栈中元素输出,后缀表达结果为输出结果逆序。
代码实现:
import java.util.*;
public class PolandNotation {
public static void main(String[] args) {
//验证:给定后缀表达式完成四则运算
//输入后缀表达式,每个数字和符号中间用空格隔开
String suffixExpression ="1 2.0 3 * - 5.8 3 * 11 - 2 * 1 - +";//(1-2*3)+((5.8*3-11)*2-1)
// 将后缀表达式字符串存入到列表中
List<String> sufeList1 = getList(suffixExpression);
System.out.println("后缀表达式="+sufeList1);
//根据已知的后缀表达式计算结果
float res1 = calculate(sufeList1);
System.out.println("计算结果="+ res1);
//验证:给定中缀表达式完成四则运算
//给定中缀表达式,将其字符串存入到列表中
String infixExpression= "(1-2.0*3)+((5.8*3-11)*2-1)";
List<String> infeList = infixExpressionToList(infixExpression);
System.out.println("中缀表达式="+infeList);
//将中缀表达式转换成后缀表达式并存入列表
List<String> sufeList2 = infixTosuffix(infeList);
System.out.println("后缀表达式="+sufeList2);
//根据转换的后缀表达式计算结果
float res2 = calculate(sufeList2);
System.out.println("计算结果="+ res2);
}
/**
* 将中缀表达式存储到列表中,便于后面转换成后缀表达式处理
* @param s 中缀表达式字符串
* @return 存储分割后的中缀表达式的列表
*/
public static List<String> infixExpressionToList(String s){
List<String> infelist = new ArrayList<>();
int index = 0;
String ss;
char c;
do {
if((c=s.charAt(index))!='.' && !Character.isDigit(c=s.charAt(index))) {//判断是否为数字或小数点
//如果不是,那么就是运算符号或者括号,转成字符转字符串并直接放入列表
infelist.add(c+"");
index++;
}else {//如果是数字或小数点,需要拼接成完整数
ss = "";
//注意需要判断index是否指向超出字符串长度
while(index<s.length() && (Character.isDigit(c=s.charAt(index)) || (c=s.charAt(index))=='.')) {
ss += c;
index++;
}
infelist.add(ss);
}
}while(index < s.length());
return infelist;
}
/**
* 将中缀表达式转换成后缀表达式
* 存在问题:负数不能直接参与计算(eg:-5),需要加0(eg:0-5) >>> 需要改进的地方
* @param ls 中缀表达式列表
* @return 后缀表达式列表
*/
public static List<String> infixTosuffix(List<String> infixls){
Stack<String> s1 = new Stack<>();
Stack<String> s2 = new Stack<>();
List<String> suffixls = new ArrayList<>();
for(String item:infixls) {
if(item.matches("^[+-]?\\d+(\\.\\d+)?$")) {//如果是数字,直接压入栈s1
s2.push(item);
}else if(item.equals("(")) {//如果是左括号,直接压入栈s1
s1.push(item);
}else if(item.equals(")")) {//如果是右括号,弹出栈s1元素直到遇到第一个“(”停止,并将弹出元素压入栈s2
while(!(s1.peek()).equals("(")) {//如果没遇到左括号,弹出s1然后压入s2
s2.push(s1.pop());
}
s1.pop();//弹出左括号丢弃
}else{//如果是运算符号
if(s1.isEmpty() || (s1.peek()).equals("(")) {//case1:s1站空或栈顶元素为左括号,直接压入栈s1
s1.push(item);
}else {//case2:需要比较优先级
if(priority(item) > priority(s1.peek())) {//如果扫描的运算符优先级高于栈顶元素,直接压入栈s1
s1.push(item);
}else {
s2.push(s1.pop());//弹出栈s1栈顶元素压入栈s2
//当非空非左括号且扫描运算发优先级不大于栈顶符号,继续判断优先级
while(!s1.isEmpty() && !(s1.peek()).equals("(") && priority(item) <= priority(s1.peek())) {
s2.push(s1.pop());
}
s1.push(item);
}
}
}
}
while(!s1.isEmpty()) {//将栈s1依次弹出剩余元素压入栈s2
s2.push(s1.pop());
}
//弹出栈2元素存入列表中并反转列表返回
while(!s2.isEmpty()) {
suffixls.add(s2.pop());
}
Collections.reverse(suffixls);
return suffixls;
}
/**
* 将后缀表达式字符串分割后存储在列表中
* @param suffixExpression 后缀表达式字符串
* @return 存储后缀表达式的列表
*/
public static List<String> getList(String suffixExpression){
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<String>();
for(String s:split){
list.add(s);
}
return list;
}
/**
* 判断运算符号优先级,返回值越大优先级越高
* @param oper 运算符号字符串格式
* @return 1,0,-1值越大优先级越高
*/
public static int priority(String oper) {
if(oper.equals("*") || oper.equals("/")) {
return 1;
}else if(oper.equals("+") || oper.equals("-")) {
return 0;
}else {
return -1;
}
}
/**
* 完成四则运算
* @param list 存储后缀表达式的列表
* @return 计算结果
*/
public static float calculate(List<String> list) {
Stack<String> stack = new Stack<>();
for(String item:list) {
//用正则表达式匹配,此处可匹配正负数和小数
if(item.matches("^[+-]?\\d+(\\.\\d+)?$")) {
stack.push(item);
}else {
float num1 = Float.parseFloat(stack.pop());
float num2 = Float.parseFloat(stack.pop());
float res = 0;
if(item.equals("+")) {
res = num1 + num2;
}else if(item.equals("-")) {
res = num2 - num1;
}else if(item.equals("*")) {
res = num1 * num2;
}else if(item.equals("/")){
res = num2 / num1;
}else {
throw new RuntimeException("运算符号不对劲啊");
}
stack.push(String.valueOf(res));
}
}
return Float.parseFloat(stack.pop());
}
}
Quiet and Quick, Salute!