Java中綴表達式轉后綴表達式實現(xiàn)方法詳解
更新時間：2019年03月23日 11:09:44 作者：水中魚之1999
這篇文章主要介紹了Java中綴表達式轉后綴表達式實現(xiàn)方法,結合實例形式分析了Java中綴表達式轉換成后綴表達式的相關算法原理與具體實現(xiàn)技巧,需要的朋友可以參考下
本文實例講述了Java中綴表達式轉后綴表達式實現(xiàn)方法。分享給大家供大家參考，具體如下：
本文先給出思路與方法，最后將給出完整代碼
項目實戰(zhàn)：
http://www.dbjr.com.cn/article/158335.htm
算法綜述：
一、中綴表達式轉后綴表達式：
1.中綴表達式要轉后綴表達式，首先需要兩個Stack（棧），其中一個應用于存放字符，另一個用于存放數(shù)字。
2.讀到數(shù)字直接存入數(shù)字棧中，讀到字符時，要咸魚棧內(nèi)前一元素（字符）進行比較，當當前（要存入的字符）優(yōu)先級大于遷移字符時才存入，否則（>=）要仿佛將棧內(nèi)元素彈出，并依次存入數(shù)字棧中。
提示：‘（' 的優(yōu)先級默認比所有字符都小。所有字符都可以存在它后面；同時夜筆所有字符都大，可以存在所有字符后面
3.遇到 ‘）'時將棧內(nèi)所有字符依次彈出，并存入數(shù)字棧中，知道遇到 ‘（' 為止
4.當所有字符、數(shù)字訪問完畢時，棧內(nèi)很可能還會有剩余的字符，這是將他們一次彈出，并純?nèi)鐢?shù)字棧中
小技巧：
1.存放‘+'，‘-'時，如果只有當前一個數(shù)位空或者‘（' 時才進行存入操作，否則均彈出。
2.存放 ‘*'，‘/' 時，只有當前一個數(shù)位 ‘*'，‘/' 時才彈出其他情況下，均存入。
附上代碼：
/*
* 中綴轉后綴
*/
public void toPostfix() {
// TODO Auto-generated method stub
int sum = 0 ;//用于記入”（）“總個數(shù)
int j = 0 ;//用于讀到”）“時循環(huán)出棧
String outStack = null;
charnum.push(null);
for( int i = 0 ; i < calculateLength ; i ++){
if ( calculate[i].equals("(")) {
charnum.push(calculate[i]);
sum ++ ;
}else if ( calculate[i].equals(")") ) {
outStack = charnum.pop();//進入前先出一個
while ( !outStack.equals("(") ){
num.push(outStack);
outStack = charnum.pop();
}//最后一次outStack正好接到”（“不入棧
sum ++ ;
}else if (calculate[i].equals("*")) {
outStack = charnum.pop();
charnum.push(outStack);
while( ( outStack == "*" || outStack == "/" ) && !(outStack == null) ){
num.push(outStack);
charnum.pop();//由于前第三行又將outStack存入棧中，座椅此處再次彈出
outStack = charnum.pop();
charnum.push(outStack);
}
charnum.push("*");
}else if (calculate[i].equals("/")) {
outStack = charnum.pop();
charnum.push(outStack);
while( ( outStack == "*" || outStack == "/" ) && !(outStack == null) ){
num.push(outStack);
charnum.pop();//由于前第三行又將outStack存入棧中，座椅此處再次彈出
outStack = charnum.pop();
charnum.push(outStack);
}
charnum.push("/");
}else if (calculate[i].equals("+")) {
outStack = charnum.pop();
charnum.push(outStack);
while( !(outStack=="(") && !(outStack == null) ){
num.push(outStack);
charnum.pop();
outStack = charnum.pop();
charnum.push(outStack);
}
charnum.push("+");
}else if (calculate[i].equals("-")) {
outStack = charnum.pop();
charnum.push(outStack);
while( !(outStack=="(") && !(outStack == null) ){
num.push(outStack);
charnum.pop();
outStack = charnum.pop();
charnum.push(outStack);
}
charnum.push("-");
}else {
num.push(calculate[i]);
}
}
outStack = charnum.pop();
while ( outStack != null ) {
num.push(outStack);
outStack = charnum.pop();
}
calculateLength = calculateLength - sum ;
Stack<String> zanshi = new Stack<>();
for(int i = 0 ; i < calculateLength ; i ++ ){
zanshi.push(num.pop());
}
CalculateToZero();
for(int i = 0 ; i < calculateLength ;i ++ ){
calculate[i] = zanshi.pop();
}
}
二、后綴表達式計算
后綴表達式計算只遵循一個原則：
首先將表達式存在棧中
遇到符號時彈出兩個相應的數(shù)字，進行計算后再次 存入棧內(nèi)
最后棧內(nèi)身下的唯一一個數(shù)，就是所要求的結果
/*
* 后綴表達式求值
*/
public String postfix() {
int a = 0 , b = 0;//棧中彈出的兩數(shù)
int sum ;//求兩數(shù)運算
for (int i = 0; i < calculateLength ; i++ ) {
if (i == 0) {
num.push(calculate[i]);
}else if (calculate[i].equals("+") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a + b ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("-") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a - b ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("*") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a * b ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("/") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a / b ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("%") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a / b ;
num.push(String.valueOf(sum));
}else {
num.push(calculate[i]);
}
}
return num.pop();
}
}
最后附上完整代碼
//注：代碼中有很多輸出 方便讀者實時查看運算過程中 各內(nèi)容
// 這些輸出導致篇幅較長 大家看明白后 刪去即可
public class Calculate {
private Stack<String> num; //后綴用棧 中轉后數(shù)字棧
private Stack<String> charnum;//中轉后字符棧
private String []calculate;//存字符串數(shù)組
private int calculateLength;//字符串數(shù)組長度
public Calculate() {
// TODO Auto-generated constructor stub
num = new Stack<>(); //后綴用棧 中轉后數(shù)字棧
charnum = new Stack<>();//中轉后字符棧
calculate = new String[1000];//存字符串數(shù)組
calculateLength = 0 ;//字符串數(shù)組長度
}
//轉字符串數(shù)組
public void toStringArray(String input) {
boolean pointFalg = false;
char charArray[] = input.toCharArray();
double number = 0;//用于導入多位數(shù)
int j = 0 ;//用于計入當前字符串數(shù)組的位數(shù)
int sizeOfArray = charArray.length;
int pointBelow =1
;
for(int i = 0 ; i < sizeOfArray ; i++){
if(charArray[i] == '('){
calculate[j++] = "(";
}else if(charArray[i] == ')'){
calculate[j++] = ")";
}else if (charArray[i] == '+') {
calculate[j++] = "+";
}else if (charArray[i] == '-') {
calculate[j++] = "-";
}else if (charArray[i] == '*') {
calculate[j++] = "*";
}else if (charArray[i] == '/') {
calculate[j++] = "/";
}else if (charArray[i] == '%') {
calculate[j++] = "%";
}else if (charArray[i] == '#') {
calculate[j++] = "#";
}else if (charArray[i] == '.') {
System.out.println("find new . :");
pointBelow = 1;
// sizeOfArray -- ;
pointFalg = true;
}else {
String str=String.valueOf(charArray[i]);
if (pointFalg == false) {
System.out.println("1:" + number);
number = number * 10 + Double.parseDouble(str);
}else {
System.out.println("2:" + charArray[i]);
number = number + Double.parseDouble(str) * Math.pow(0.1, pointBelow);
}
System.out.println("3:" + number + "i==" + i);
if( (i + 1) == sizeOfArray ||( charArray[i+1] < '0' || charArray[i+1] > '9' ) && charArray[i+1] != '.'){
if ( (i + 1) != sizeOfArray && charArray[i+1] == ' ') {
i++;
}
calculate[j++] = String.valueOf(number);
System.out.println("number:" + number);
number = 0 ;
pointFalg = false;
}
}
System.out.println("---z->" + calculate[i]);
}
calculateLength = j-- ;//不--會將‘#'存入
}
public void outPutCalculate() {
for(int i = 0 ; i < calculateLength ; i ++ ){
System.out.println(calculate[i]);
}
}
public void CalculateToZero() {
for(int i = 0 ; i < calculateLength ; i ++ ){
calculate[i]= calculate[999] ;
}
}
//中綴轉后綴
public void toPostfix() {
// TODO Auto-generated method stub
System.out.println("789");
int sum = 0 ;//用于記入”（）“總個數(shù)
int j = 0 ;//用于讀到”）“時循環(huán)出棧
String outStack = null;
charnum.push(null);
System.out.println(calculateLength);
for( int i = 0 ; i < calculateLength ; i ++){
System.out.println(calculate[i]);//-----------------------------
if ( calculate[i].equals("(")) {
charnum.push(calculate[i]);
System.out.println("1-1 charpush " + calculate[i]);//-----------------------------
sum ++ ;
}else if ( calculate[i].equals(")") ) {
System.out.println("2-1 charpush " + calculate[i]);//-----------------------------
outStack = charnum.pop();//進入前先出一個
System.out.println("2-1 charpush " + outStack);//-----------------------------
while ( !outStack.equals("(") ){
System.out.println("2-2 charpush " + outStack);//-----------------------------
num.push(outStack);
outStack = charnum.pop();
}//最后一次outStack正好接到”（“不入棧
System.out.println("qiangxing 1 = " + outStack );
// outStack = charnum.pop();
System.out.println("qiangxing 2 = " + outStack );
sum ++ ;
}else if (calculate[i].equals("*")) {
outStack = charnum.pop();
charnum.push(outStack);
System.out.println("3-2 charpush " + outStack);//-----------------------------
while( ( outStack == "*" || outStack == "/" || outStack == "%" ) && !(outStack == null) ){
System.out.println("3-1 charpush " + outStack);//-----------------------------
num.push(outStack);
charnum.pop();//由于前第三行又將outStack存入棧中，座椅此處再次彈出
outStack = charnum.pop();
charnum.push(outStack);
}
System.out.println("3-3 charpush " + outStack);//-----------------------------
charnum.push("*");
}else if (calculate[i].equals("%")) {
outStack = charnum.pop();
charnum.push(outStack);
System.out.println("3-2 charpush " + outStack);//-----------------------------
while( ( outStack == "*" || outStack == "/" || outStack == "%" ) && !(outStack == null) ){
System.out.println("3-1 charpush " + outStack);//-----------------------------
num.push(outStack);
charnum.pop();//由于前第三行又將outStack存入棧中，座椅此處再次彈出
outStack = charnum.pop();
charnum.push(outStack);
}
System.out.println("3-3 charpush " + outStack);//-----------------------------
charnum.push("%");
}else if (calculate[i].equals("/")) {
System.out.println("5-1-0 charpush " + "1-1-1-1-1-1-1-1");//-----------------------------
outStack = charnum.pop();
System.out.println("5-1-1 charpush " + "2-2-2-2-2-2-22-2");//-----------------------------
charnum.push(outStack);
System.out.println("4-1 charpush " + outStack);//-----------------------------
while( ( outStack == "*" || outStack == "/" || outStack == "%") && !(outStack == null) ){
System.out.println("4-2 charpush " + outStack);//-----------------------------
num.push(outStack);
charnum.pop();//由于前第三行又將outStack存入棧中，座椅此處再次彈出
outStack = charnum.pop();
charnum.push(outStack);
}
System.out.println("4-3 charpush " + outStack);//-----------------------------
System.out.println("5-1-2 charpush " + outStack);//-----------------------------
charnum.push("/");
}else if (calculate[i].equals("+")) {
outStack = charnum.pop();
charnum.push(outStack);
System.out.println("5-1 charpush " + outStack);//-----------------------------
while( !(outStack=="(") && !(outStack == null) ){
System.out.println("5-2 charpush " + outStack);//-----------------------------
num.push(outStack);
charnum.pop();
outStack = charnum.pop();
charnum.push(outStack);
}
System.out.println("5-3 charpush " + outStack);//-----------------------------
charnum.push("+");
}else if (calculate[i].equals("-")) {
outStack = charnum.pop();
charnum.push(outStack);
System.out.println("6-1 charpush " + outStack);//-----------------------------
while( !(outStack=="(") && !(outStack == null) ){
System.out.println("6-2 charpush " + outStack);//-----------------------------
num.push(outStack);
charnum.pop();
outStack = charnum.pop();
charnum.push(outStack);
}
System.out.println("6-3 charpush " + outStack);//-----------------------------
charnum.push("-");
}else {
System.out.println("7-7 " + calculate[i]);
num.push(calculate[i]);
}
}
System.out.println("匹配結束" + outStack);
outStack = charnum.pop();
System.out.println("finish 1 == " + outStack);
while ( outStack != null ) {
num.push(outStack);
outStack = charnum.pop();
System.out.println("finish 2 == " + outStack);
}
calculateLength = calculateLength - sum ;
System.out.println( "0.0.0.0 charpush " );//-----------------------------
System.out.println("sum = " + sum + " calculate = " +
calculateLength + "calculateLength-sum = " + (calculateLength-sum));
System.out.println("over ~~~~~0 ");
Stack<String> zanshi = new Stack<>();
// num.pop();
for(int i = 0 ; i < calculateLength ; i ++ ){
zanshi.push(num.pop());
// System.out.println(num.pop());
}
CalculateToZero();
System.out.println("over ~~~~~1 ");
for(int i = 0 ; i < calculateLength ;i ++ ){
calculate[i] = zanshi.pop();
}
System.out.println("over ~~~~~2 ");
for(int i = 0 ; i < calculateLength ;i ++ ){
System.out.println(calculate[i]);
}
System.out.println("over ~~~~~3 ");
// num.push("#");
}
//后綴計算
public String postfix() {
BigDecimal a , b ;//棧中彈出的兩數(shù)
BigDecimal sum ;//求兩數(shù)運算
for (int i = 0; i < calculateLength ; i++ ) {
// System.out.println("目前符號：" + calculate[i]);
if (i == 0) {
num.push(calculate[i]);
}else if (calculate[i].equals("+") ) {
b = new BigDecimal(num.pop());
a = new BigDecimal(num.pop());
sum = a.add(b) ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("-") ) {
b = new BigDecimal(num.pop());
a = new BigDecimal(num.pop());
sum = a.subtract(b) ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("*") ) {
b = new BigDecimal(num.pop());
a = new BigDecimal(num.pop());
sum = a.multiply(b) ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("/") ) {
b = new BigDecimal(num.pop());
a = new BigDecimal(num.pop());
sum = a.divide(b,10,RoundingMode.HALF_UP) ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("%") ) {
b = new BigDecimal(num.pop());
a = new BigDecimal(num.pop());
sum = a.divideAndRemainder(b)[1] ;
num.push(String.valueOf(sum));
}else {
num.push(calculate[i]);
}
}
return num.pop();
}
}
結果如下：
一、前綴轉后綴并輸出
其中over前為轉化后的后綴表達式
over后為計算結果
public class Main {
public static void main(String[] args) {
Calculate text = new Calculate();
text.toStringArray("1+2*(3-1+2)-3");
text.outPutCalculate();
text.toPostfix();
System.out.println(text.postfix());
}
}
二、后綴直接輸出
注意后綴表達式時
為了實現(xiàn)多位數(shù)運算，連續(xù)輸入一串數(shù)時 ，輸入完一個數(shù)加空格
如：要計算："1+2*(3-1+2)-3" 則輸入："1 2 3 1-2+*+3-"
例：
public class Main {
public static void main(String[] args) {
Calculate text = new Calculate();
text.toStringArray("1 2 3 1-2+*+3-");
text.outPutCalculate();
System.out.println(text.postfix());
}
}
輸出結果：
更多關于java算法相關內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結構與算法教程》、《Java操作DOM節(jié)點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設計有所幫助。
相關文章
這篇文章主要介紹了通過實例解析java8中的parallelStream,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-11-11
這篇文章主要介紹了SpringIOC容器中bean的作用范圍和生命周期,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-02-02
這篇文章主要介紹了SpringBoot本地磁盤映射問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-10-10
tomcat目錄結構簡介_動力節(jié)點Java學院整理
這篇文章主要介紹了tomcat目錄結構簡介_動力節(jié)點Java學院整理的相關資料,需要的朋友可以參考下2017-07-07
基于Spring + Spring MVC + Mybatis 高性能web構建實例詳解
這篇文章主要介紹了基于Spring + Spring MVC + Mybatis 高性能web構建實例詳解,需要的朋友可以參考下2017-04-04
如何使用IDEA2022.1?創(chuàng)建Spring?Boot項目
這篇文章主要介紹了如何使用IDEA2022.1?創(chuàng)建Spring?Boot項目,大家在使用idea開發(fā)工具時發(fā)現(xiàn)給以往的版本略微的不同，細心的小編在此記錄下，需要的朋友可以參考下2022-08-08
java實現(xiàn)word文檔轉pdf并添加水印的方法詳解
這篇文章主要介紹了java實現(xiàn)word文檔轉pdf并添加水印的方法,結合實例形式詳細分析了java word文檔轉PDF相關實現(xiàn)技巧與操作注意事項,需要的朋友可以參考下2019-09-09
基于JPA實體類監(jiān)聽器@EntityListeners注解的使用實例
這篇文章主要介紹了JPA實體類監(jiān)聽器@EntityListeners注解的使用實例，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
SpringBoot+actuator和admin-UI實現(xiàn)監(jiān)控中心方式
這篇文章主要介紹了SpringBoot+actuator和admin-UI實現(xiàn)監(jiān)控中心方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-05-05
在Java中實現(xiàn)讓線程按照自己指定的順序執(zhí)行
這篇文章主要介紹了在Java中實現(xiàn)讓線程按照自己指定的順序執(zhí)行，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06