中綴表達(dá)式怎么轉(zhuǎn)成后綴表達(dá)式塘偎？
- 1）初始化兩個(gè)棧，分別用于存儲(chǔ)后綴表達(dá)式結(jié)果S2和利用S1棧完成運(yùn)算符號(hào)的指定位置輸出易稠；
- 2）從左往右掃描中綴表達(dá)式缸废，當(dāng)掃描到數(shù)字時(shí)，直接壓入到S2棧中驶社；
- 3）當(dāng)掃描到運(yùn)算符號(hào)時(shí)（不包括括號(hào)）:
- case1: 如果S1棧為空或者棧頂符號(hào)為“（”時(shí)企量，直接將掃描的運(yùn)算符號(hào)壓入到棧S1中；
- case2: 如果不是case1情況亡电，比較掃描到的符號(hào)與S1棧頂符號(hào)的優(yōu)先級(jí)届巩，如果優(yōu)先級(jí)高于棧頂符號(hào)，則直接壓入棧S1逊抡；否則姆泻，彈出S1棧頂符號(hào)并壓入S2棧中零酪，返回地 3）繼續(xù)與S1棧頂符號(hào)比較冒嫡；
- 4）當(dāng)掃描到括號(hào)時(shí)（包括左右括號(hào)）：
- case1:如果是左括號(hào)“（”，則直接壓入棧S1中四苇；
- case2:如果是右括號(hào)“）”孝凌，則依次彈出棧S1棧頂符號(hào)并壓入S2棧中，直至S1棧頂元素為左括號(hào)“（”月腋，彈出棧頂符號(hào)（即左括號(hào)）丟棄蟀架；
- 5）重復(fù)2）3）4）步驟瓣赂，直至掃描到中綴表達(dá)式最后一位，將棧S1中所有符號(hào)彈出并依次壓入到S2棧中片拍；
- 6）依次彈出S2棧中元素輸出煌集，后綴表達(dá)結(jié)果為輸出結(jié)果逆序。
具體代碼實(shí)現(xiàn)如下：
import java.util.*;
public class PolandNotation {
public static void main(String[] args) {
//驗(yàn)證：給定后綴表達(dá)式完成四則運(yùn)算
//輸入后綴表達(dá)式,每個(gè)數(shù)字和符號(hào)中間用空格隔開
String suffixExpression ="1 2.0 3 * - 5.8 3 * 11 - 2 * 1 - +";//（1-2*3）+（（5.8*3-11）*2-1）
// 將后綴表達(dá)式字符串存入到列表中
List<String> sufeList1 = getList(suffixExpression);
System.out.println("后綴表達(dá)式="+sufeList1);
//根據(jù)已知的后綴表達(dá)式計(jì)算結(jié)果
float res1 = calculate(sufeList1);
System.out.println("計(jì)算結(jié)果="+ res1);
//驗(yàn)證：給定中綴表達(dá)式完成四則運(yùn)算
//給定中綴表達(dá)式捌省，將其字符串存入到列表中
String infixExpression= "(1-2.0*3)+((5.8*3-11)*2-1)";
List<String> infeList = infixExpressionToList(infixExpression);
System.out.println("中綴表達(dá)式="+infeList);
//將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式并存入列表
List<String> sufeList2 = infixTosuffix(infeList);
System.out.println("后綴表達(dá)式="+sufeList2);
//根據(jù)轉(zhuǎn)換的后綴表達(dá)式計(jì)算結(jié)果
float res2 = calculate(sufeList2);
System.out.println("計(jì)算結(jié)果="+ res2);
}
/**
* 將中綴表達(dá)式存儲(chǔ)到列表中苫纤，便于后面轉(zhuǎn)換成后綴表達(dá)式處理
* @param s 中綴表達(dá)式字符串
* @return 存儲(chǔ)分割后的中綴表達(dá)式的列表
*/
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))) {//判斷是否為數(shù)字或小數(shù)點(diǎn)
//如果不是，那么就是運(yùn)算符號(hào)或者括號(hào),轉(zhuǎn)成字符轉(zhuǎn)字符串并直接放入列表
infelist.add(c+"");
index++;
}else {//如果是數(shù)字或小數(shù)點(diǎn)纲缓，需要拼接成完整數(shù)
ss = "";
//注意需要判斷index是否指向超出字符串長(zhǎng)度
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;
}
/**
* 將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式
* 存在問題：負(fù)數(shù)不能直接參與計(jì)算（eg:-5）,需要加0(eg:0-5) >>> 需要改進(jìn)的地方
* @param ls 中綴表達(dá)式列表
* @return 后綴表達(dá)式列表
*/
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+)?$")) {//如果是數(shù)字卷拘，直接壓入棧s1
s2.push(item);
}else if(item.equals("(")) {//如果是左括號(hào)，直接壓入棧s1
s1.push(item);
}else if(item.equals(")")) {//如果是右括號(hào)祝高，彈出棧s1元素直到遇到第一個(gè)“（”停止栗弟，并將彈出元素壓入棧s2
while(!(s1.peek()).equals("(")) {//如果沒遇到左括號(hào),彈出s1然后壓入s2
s2.push(s1.pop());
}
s1.pop();//彈出左括號(hào)丟棄
}else{//如果是運(yùn)算符號(hào)
if(s1.isEmpty() || (s1.peek()).equals("(")) {//case1:s1站空或棧頂元素為左括號(hào)，直接壓入棧s1
s1.push(item);
}else {//case2:需要比較優(yōu)先級(jí)
if(priority(item) > priority(s1.peek())) {//如果掃描的運(yùn)算符優(yōu)先級(jí)高于棧頂元素工闺，直接壓入棧s1
s1.push(item);
}else {
s2.push(s1.pop());//彈出棧s1棧頂元素壓入棧s2
//當(dāng)非空非左括號(hào)且掃描運(yùn)算發(fā)優(yōu)先級(jí)不大于棧頂符號(hào)乍赫，繼續(xù)判斷優(yōu)先級(jí)
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元素存入列表中并反轉(zhuǎn)列表返回
while(!s2.isEmpty()) {
suffixls.add(s2.pop());
}
Collections.reverse(suffixls);
return suffixls;
}
/**
* 將后綴表達(dá)式字符串分割后存儲(chǔ)在列表中
* @param suffixExpression 后綴表達(dá)式字符串
* @return 存儲(chǔ)后綴表達(dá)式的列表
*/
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;
}
/**
* 判斷運(yùn)算符號(hào)優(yōu)先級(jí)，返回值越大優(yōu)先級(jí)越高
* @param oper 運(yùn)算符號(hào)字符串格式
* @return 1陆蟆，0耿焊，-1值越大優(yōu)先級(jí)越高
*/
public static int priority(String oper) {
if(oper.equals("*") || oper.equals("/")) {
return 1;
}else if(oper.equals("+") || oper.equals("-")) {
return 0;
}else {
return -1;
}
}
/**
* 完成四則運(yùn)算
* @param list 存儲(chǔ)后綴表達(dá)式的列表
* @return 計(jì)算結(jié)果
*/
public static float calculate(List<String> list) {
Stack<String> stack = new Stack<>();
for(String item:list) {
//用正則表達(dá)式匹配，此處可匹配正負(fù)數(shù)和小數(shù)
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("運(yùn)算符號(hào)不對(duì)勁啊");
}
stack.push(String.valueOf(res));
}
}
return Float.parseFloat(stack.pop());
}
}
Quiet and Quick, Salute!
