java實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)后綴的方法
更新時(shí)間：2018年11月28日 14:53:03 作者：水中魚之1999
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)后綴的表達(dá)式方法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
本文先給出思路與方法，最后將給出完整代碼：
算法綜述：
一、中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式：
1.中綴表達(dá)式要轉(zhuǎn)后綴表達(dá)式，首先需要兩個(gè)Stack（棧），其中一個(gè)應(yīng)用于存放字符，另一個(gè)用于存放數(shù)字。
2.讀到數(shù)字直接存入數(shù)字棧中，讀到字符時(shí)，要咸魚棧內(nèi)前一元素（字符）進(jìn)行比較，當(dāng)當(dāng)前（要存入的字符）優(yōu)先級(jí)大于遷移字符時(shí)才存入，否則（>=）要仿佛將棧內(nèi)元素彈出，并依次存入數(shù)字棧中。
提示：‘（' 的優(yōu)先級(jí)默認(rèn)比所有字符都小。所有字符都可以存在它后面；同時(shí)夜筆所有字符都大，可以存在所有字符后面
3.遇到 ‘）'時(shí)將棧內(nèi)所有字符依次彈出，并存入數(shù)字棧中，知道遇到 ‘（' 為止
4.當(dāng)所有字符、數(shù)字訪問完畢時(shí)，棧內(nèi)很可能還會(huì)有剩余的字符，這是將他們一次彈出，并純?nèi)鐢?shù)字棧中
小技巧：
1.存放‘+'，‘-'時(shí)，如果只有當(dāng)前一個(gè)數(shù)位空或者‘（' 時(shí)才進(jìn)行存入操作，否則均彈出。
2.存放 ‘*'，‘/' 時(shí)，只有當(dāng)前一個(gè)數(shù)位 ‘*'，‘/' 時(shí)才彈出其他情況下，均存入。
附上代碼：
/*
* 中綴轉(zhuǎn)后綴
*/
public void toPostfix() {
// TODO Auto-generated method stub
int sum = 0 ;//用于記入”（）“總個(gè)數(shù)
int j = 0 ;//用于讀到”）“時(shí)循環(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();//進(jìn)入前先出一個(gè)
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();
}
}
二、后綴表達(dá)式計(jì)算
后綴表達(dá)式計(jì)算只遵循一個(gè)原則：
首先將表達(dá)式存在棧中
遇到符號(hào)時(shí)彈出兩個(gè)相應(yīng)的數(shù)字，進(jìn)行計(jì)算后再次 存入棧內(nèi)
最后棧內(nèi)身下的唯一一個(gè)數(shù)，就是所要求的結(jié)果
/*
* 后綴表達(dá)式求值
*/
public String postfix() {
int a = 0 , b = 0;//棧中彈出的兩數(shù)
int sum ;//求兩數(shù)運(yùn)算
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();
}
}
最后附上完整代碼
//注：代碼中有很多輸出 方便讀者實(shí)時(shí)查看運(yùn)算過程中 各內(nèi)容
// 這些輸出導(dǎo)致篇幅較長 大家看明白后 刪去即可
public class Text {
Stack<String> num = new Stack<>(); //后綴用棧 中轉(zhuǎn)后數(shù)字棧
Stack<String> charnum = new Stack<>();//中轉(zhuǎn)后字符棧
String []calculate = new String[1000];//存字符串?dāng)?shù)組
int calculateLength = 0 ;//字符串?dāng)?shù)組長度
public Text() {
// TODO Auto-generated constructor stub
}
//轉(zhuǎn)字符串?dāng)?shù)組
public void toStringArray(String input) {
char charArray[] = input.toCharArray();
int number = 0;//用于導(dǎo)入多位數(shù)
int j = 0 ;//用于計(jì)入當(dāng)前字符串?dāng)?shù)組的位數(shù)
System.out.println(charArray.length);
for(int i = 0 ; i < charArray.length ; 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 {
String str=String.valueOf(charArray[i]);
number = number * 10 + Integer.parseInt(str);System.out.println("123");
if( (i + 1) == charArray.length || charArray[i+1] < '0' || charArray[i+1] > '9'){
if ( (i + 1) != charArray.length && charArray[i+1] == ' ') {
System.out.println("456");i++;
}
calculate[j++] = String.valueOf(number);
System.out.println(number);
number = 0 ;
}
}
System.out.println("---z->" + calculate[i]);
}
calculateLength = j-- ;//不--會(huì)將‘#'存入
}
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] ;
}
}
//中綴轉(zhuǎn)后綴
public void toPostfix() {
// TODO Auto-generated method stub
System.out.println("789");
int sum = 0 ;//用于記入”（）“總個(gè)數(shù)
int j = 0 ;//用于讀到”）“時(shí)循環(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();//進(jìn)入前先出一個(gè)
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 == 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 == 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("匹配結(jié)束" + 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("#");
}
//后綴計(jì)算
public String postfix() {
int a = 0 , b = 0;//棧中彈出的兩數(shù)
int sum ;//求兩數(shù)運(yùn)算
for (int i = 0; i < calculateLength ; i++ ) {
// System.out.println("目前符號(hào)：" + calculate[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();
}
}
結(jié)果如下：
一、前綴轉(zhuǎn)后綴并輸出
其中over前為轉(zhuǎn)化后的后綴表達(dá)式
over后為計(jì)算結(jié)果
public class Main {
public static void main(String[] args) {
Text text = new Text();
text.toStringArray("1+2*(3-1+2)-3");
text.outPutCalculate();
text.toPostfix();
System.out.println(text.postfix());
}
}
二、后綴直接輸出
注意后綴表達(dá)式時(shí)
為了實(shí)現(xiàn)多位數(shù)運(yùn)算，連續(xù)輸入一串?dāng)?shù)時(shí) ，輸入完一個(gè)數(shù)加空格
如：要計(jì)算："1+2*(3-1+2)-3" 則輸入："1 2 3 1-2+*+3-"
例：
public class Main {
public static void main(String[] args) {
Text text = new Text();
text.toStringArray("1 2 3 1-2+*+3-");
text.outPutCalculate();
System.out.println(text.postfix());
}
}
輸出結(jié)果：
以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
您可能感興趣的文章:
相關(guān)文章
Java?MapStruct優(yōu)雅地實(shí)現(xiàn)對(duì)象轉(zhuǎn)換
MapSturct?是一個(gè)生成類型安全，高性能且無依賴的?JavaBean?映射代碼的注解處理器，用它可以輕松實(shí)現(xiàn)對(duì)象轉(zhuǎn)換，下面就來和大家聊聊具體操作吧2023-06-06
這篇文章主要介紹了IntelliJ IDEA 中必有得插件和配置,本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-05-05
這篇文章主要為大家介紹了java睡眠排序算法的示例實(shí)現(xiàn)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步2022-02-02
java?poi導(dǎo)入純數(shù)字等格式問題及解決
這篇文章主要介紹了java?poi導(dǎo)入純數(shù)字等格式問題及解決，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-03-03
SpringCloud openfeign相互調(diào)用實(shí)現(xiàn)方法介紹
在springcloud中，openfeign是取代了feign作為負(fù)載均衡組件的，feign最早是netflix提供的，他是一個(gè)輕量級(jí)的支持RESTful的http服務(wù)調(diào)用框架，內(nèi)置了ribbon，而ribbon可以提供負(fù)載均衡機(jī)制，因此feign可以作為一個(gè)負(fù)載均衡的遠(yuǎn)程服務(wù)調(diào)用框架使用2022-11-11
SpringBoot啟動(dòng)yaml報(bào)錯(cuò)的解決
這篇文章主要介紹了SpringBoot啟動(dòng)yaml報(bào)錯(cuò)的解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-08-08
在面向?qū)ο蟮某绦蛟O(shè)計(jì)中，我們通常使用類來創(chuàng)建對(duì)象，類中有許多成員變量和方法，它們是直接屬于對(duì)象實(shí)例的，與之對(duì)應(yīng)的還有一類成員，那就是靜態(tài)成員，本文就來和大家聊聊Java是如何定義訪問靜態(tài)成員的吧2023-05-05
Java連接MYSQL數(shù)據(jù)庫的實(shí)現(xiàn)步驟
以下的文章主要描述的是java連接MYSQL數(shù)據(jù)庫的正確操作步驟，在此篇文章里我們主要是以實(shí)例列舉的方式來引出其具體介紹2013-06-06
Springboot 讀取自定義pro文件注入static靜態(tài)變量方式
這篇文章主要介紹了Springboot 讀取自定義pro文件注入static靜態(tài)變量方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-07-07
這篇文章主要介紹了JWT原理與java操作jwt驗(yàn)證,詳細(xì)分析了JWT的基本概念、原理與java基于JWT進(jìn)行token驗(yàn)證的相關(guān)操作技巧,需要的朋友可以參考下2023-06-06