一:字首表達式的計算機求值
從右到左掃描表達式,遇到了數字,就将數字壓入堆棧,遇到運算符就将運算符壓入堆棧,彈出棧頂的兩個數,用運算符對他們做相應的計算.(棧頂元素,和次頂元素).并将結果入棧,接着重複上述的過程指導表達式的最左端,最後運算得出的值即為表達式的結果
舉個例子:(3+4)*5-6對應的字首表達式就是
-*+3456
,針對字首表達式求值步驟如下:
- 從右到左進行掃描,将6543依次壓入棧中
- 遇到
+
- 接下來是
*
- 最後是
-
二:中綴表達式
- 中綴表達式就是常見的運算表達式
- 中綴表達式的求值是最我們人最熟悉的,但是對計算機來說卻不好操作.是以,在計算結果時,往往會将中綴表達式轉換成其他表達式來操作,一般是轉成字尾表表達式
三:字尾表達式
- 字尾表達式又稱為逆波蘭表達式,與字首表達式相似,隻是運算符位于操作數之後
- 舉個例子,(3+4)*5-6的字尾表達式就是
3 4 + 5 * 6 -
應用執行個體:逆波蘭電腦,
任務:
- 輸入一個逆波蘭表達式,使用棧計算其結果
-
支援小括号和多位數整數,電腦隻支援對整數進行計算
代碼示範:
package com.qiu.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
//先定義一個逆波蘭表達式
String suffixExpression = "3 4 + 5 * 6 - ";//為了友善,逆波蘭表達式的數字和符号用空格隔開
//1.先将 suffixExpression=>放到一個arrayList中
//2.将ArrayList傳遞給一個方法,配合棧完成計算
List<String> list = getListString(suffixExpression);
System.out.println(list);
int res = calculate(list);
System.out.println(res);
}
//将逆波蘭表達式依次将資料和運算符放入到arraylist中
public static List<String> getListString(String suffixExpression){
//将suffixExpression分割
String[] splits = suffixExpression.split(" ");
ArrayList<String> arrayList = new ArrayList<>();
for (String ele : splits){
arrayList.add(ele);
}
return arrayList;
}
//完成對逆波蘭表達式的掃描,也就是周遊
public static int calculate(List<String> list){
//建立一個棧,隻需要一個棧即可
Stack<String> stack = new Stack<>();
//周遊list
for (String items :list){
//使用正規表達式取出數
if (items.matches("\\d+")){//比對的是多位數
//入棧
stack.push(items);
}else{
//pop兩個數,運算,再入棧
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res =0;
if (items.equals("+")){
res = num1+num2;
}else if (items.equals("-")){
res = num1-num2;
}else if (items.equals("*")){
res = num1*num2;
}else if (items.equals("/")){
res =num1/num2;
}else{
throw new RuntimeException("運算符有誤!");
}
//把res入棧
stack.push(""+res);
}
}
//最後留在stack中的資料是運算結果
return Integer.parseInt(stack.pop());
}
}
字尾表達式是适合計算機進行運算的,但是對人來說卻不太友好,在一個表達式特别長的情況下會顯得十分難受,是以在開發中一般都輸入中綴表達式,然後再通過程式将中綴表達式轉換成字尾表達式,供計算機執行
具體步驟如下
- 初始化兩個:運算符棧s1和儲存中間結果的棧s2
- 從左到右掃描中綴表達式
- 遇到操作數的時候,将其壓入s2
- 遇到操作符(
+-*/()
)的時候,比較其與s1棧頂運算符的優先級
(1) 如果運算符棧s1為空,或棧頂運算符為左括号"(" 則直接将此運算符入棧;
(2)否則,若優先級比棧頂運算符高,也将運算符壓入s1;
(3)否則,将s1棧頂的運算符彈出并壓入到s2中,再次轉到(4-1)與s1中的新的棧頂運算符相比較)
(4)遇到括号時:
如果是左括号“(”，則直接壓入s1
如果是右括号“)”，則依次彈出s1棧頂的運算符，并壓入s2，直到遇到左括号為止，此時将這一對括号丢棄
(5)重複步驟2至5，直到表達式的最右邊
(6)将s1中剩餘的運算符依次彈出并壓入s2
(7)依次彈出s2中的元素并輸出，結果的逆序即為中綴表達式對應的字尾表達式
畫一個示意圖解釋一下
第一步:掃描到了數字1時,直接放入棧s2中去,
第二步:掃描到了
+
,這個時候我們看s1中是否有運算符,這裡我們看到s1中并沒有資料,是以我們将運算符放在s1中
第三步:掃描到了
(
,根據步驟5.1.遇到了左括号,直接壓入s1中
第四步:還是左括号,繼續壓入s1棧中
第五步:掃描到了數字,将其壓入s2中
第六步:掃描到了
+
号,運算符的棧頂為
(
,是以直接将操作符壓入s1中去
第七步:掃描到了數字3,是以直接壓入s2中
重點來了!
第八步:我們遇到了右括号
)
,是以我們依次彈出s1的運算符,并壓入s2中去,同時抵消一個左括号
第九步:繼續向下掃描,遇到了
*
,由于棧頂元素是左括号,不做比較.是以*直接入棧s1
第十步:掃描到了數字4,直接入s2棧
第十一步:掃描到了右括号,我們需要彈出s1中的運算符到s2中,知道遇到了左括号,并将其抵消
第十二步:掃描到了一個減法
-
,這個時候我們就比較棧s1中的棧頂運算符,由于棧頂中有符号
+
,和掃描到的運算符優先級相同,是以我們将s1棧頂的運算符彈出,并雅壓入到s2中去,符号
-
,則入棧s1
第十三步:掃描到了數字,則直接壓入s2中
第十四步:由于,表達式掃描完畢了,将s1中剩餘的符号,依次壓入到s2中
最後一步:依次彈出s2中的元素,并進行輸出,結果的逆序即為中綴表達式對應的字尾表達式
代碼實作:
package com.qiu.stack;
import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;
import org.omg.CORBA.PRIVATE_MEMBER;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
//完成将一個中綴表達式轉成一個字尾表達式的功能
//1 + ( ( 2 + 3 )× 4) - 5 轉成1 2 3 + 4 * + 5 -
//2.因為直接對一個字元串操作不友善,是以我們先将這個字元串以中綴的表達式對應的list
//3.就是說1 + ( ( 2 + 3 )× 4) - 5 轉換成了一個ArrayList[1, +,( +(, 2, +, 3, ......]
//4.上述功能完成之後,我們将得到的中綴的表達式,轉成一個字尾表達式對應的list,中綴的表達式中的list中的括号還是被消除掉了
String expression = "1+((2+3)*4)-5";
List<String> list = toInfixExpressionList(expression);
System.out.println("中綴表達式對應的list:"+list);
List<String> parseSuffixExpressionList = parseSuffixExpressionList(list);
System.out.println("字尾表達式對應的list:"+parseSuffixExpressionList);
System.out.printf("expression=%d",calculate(parseSuffixExpressionList));
/*
//先定義一個逆波蘭表達式
String suffixExpression = "3 4 + 5 * 6 - ";//為了友善,逆波蘭表達式的數字和符号用空格隔開
//1.先将 suffixExpression=>放到一個arrayList中
//2.将ArrayList傳遞給一個方法,配合棧完成計算
List<String> list = getListString(suffixExpression);
System.out.println(list);
int res = calculate(list);
System.out.println(res);
*/
}
//方法:将中綴表達式轉成字尾表達式
public static List<String> parseSuffixExpressionList(List<String> ls){
//定義兩個棧s1 s2
Stack<String> s1 = new Stack<>();
//由于s2是一直在添加字元,沒有pop操作,而且需要逆序輸出,直接使用list<String>避免麻煩
// Stack<String> stack2 = new Stack<>();
List<String> s2 = new ArrayList<>();
//開始周遊ls
for (String item :ls){
//如果是一個數,加入到s2中
if(item.matches("\\d+")){
s2.add(item);
}else if (item.equals("(")){
s1.push(item);
}else if (item.equals(")")){
//我們需要彈出s1中的運算符到s2中,知道遇到了左括号,并将其抵消
while(!s1.peek().equals("(")){
s2.add(s1.pop());
}
s1.pop();//将這個左括号彈出去
}else {
//當item的運算符的優先級小于等于s1棧頂的運算符的優先級
//将s1棧頂的運算符彈出并壓入到s2中，再次轉到(4.1)與s1中新的棧頂運算符相比較；
//并且我們需要一個比較優先級的方法
while(s1.size()!= 0 && Operation.getValue(s1.peek())>=Operation.getValue(item)){
s2.add(s1.pop());//這裡的意思就是說我們在棧頂操作符的優先級大于了掃描到的運算符優先級,那就将這個棧頂元素添加到s2中去
}
//還需要将item壓入棧s1中
s1.push(item);
}
}
//将s1中剩餘的元素彈出并壓入到s2中去
while(s1.size()!= 0){
s2.add(s1.pop());
}
return s2;//因為是存放到list中的,list是有序的,是以按順序輸出就是對應的逆波蘭表達式
}
//将中綴表達式轉換成對應的list
public static List<String> toInfixExpressionList(String s){
// s:就是傳進來的字元串
//定義一個list存放非中綴表達式,對應的内容
ArrayList<String> ls = new ArrayList<>();
int i = 0;//這個是一個指針,用于周遊中綴表達式字元串
String str;//對多位數的一個拼接工作
char c;//每周遊一個字元就放入到c中
do {
//如果c是一個非數字,我們就需要加入到這個ls中去,因為周遊到的可能不是一個非數字的話那就是/*-+,或者()
if ((c =s.charAt(i))<48 || (c = s.charAt(i)) > 57){
ls.add(""+c);
i++;//i需要後移
}else{
//如果是一個數,需要考慮一個多位數的問題
str = "";//先将str置成空串
while(i < s.length() && (c =s.charAt(i))>=48 && (c = s.charAt(i))<=57){
str +=c;
i++;
}
ls.add(str);
}
}while (i < s.length());
return ls;
}
//将逆波蘭表達式依次将資料和運算符放入到arraylist中
public static List<String> getListString(String suffixExpression){
//将suffixExpression分割
String[] splits = suffixExpression.split(" ");
ArrayList<String> arrayList = new ArrayList<>();
for (String ele : splits){
arrayList.add(ele);
}
return arrayList;
}
//完成對逆波蘭表達式的掃描,也就是周遊
public static int calculate(List<String> list){
//建立一個棧,隻需要一個棧即可
Stack<String> stack = new Stack<>();
//周遊list
for (String items :list){
//使用正規表達式取出數
if (items.matches("\\d+")){//比對的是多位數
//入棧
stack.push(items);
}else{
//pop兩個數,運算,再入棧
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res =0;
if (items.equals("+")){
res = num1+num2;
}else if (items.equals("-")){
res = num1-num2;
}else if (items.equals("*")){
res = num1*num2;
}else if (items.equals("/")){
res =num1/num2;
}else{
throw new RuntimeException("運算符有誤!");
}
//把res入棧
stack.push(""+res);
}
}
//最後留在stack中的資料是運算結果
return Integer.parseInt(stack.pop());
}
}
//編寫一個類Operation,可以傳回一個運算符對應的優先級
class Operation{
private static int ADD = 1;
private static int SUB = 1;
private static int MUL = 2;
private static int DIV = 2;
//寫一個方法,用來傳回對應的優先級數字
public static int getValue(String operation){
int result =0;
switch (operation){
case "+":
result = ADD;
break;
case "-":
result = SUB;
break;
case "*":
result = MUL;
break;
case "/":
result = DIV;
break;
default:
System.out.println("不存在該運算符!");
break;
}
return result;
}
}
代碼運作如圖: