Java中缀表达式转后缀表达式实现方法详解

Java中缀表达式转后缀表达式实现方法详解

本文实例讲述了java中缀表达式转后缀表达式实现方法。分享给大家供大家参考，具体如下：

本文先给出思路与方法，最后将给出完整代码

项目实战：

https://jb51.net/article/158335.htm

算法综述：

一、中缀表达式转后缀表达式：

1.中缀表达式要转后缀表达式，首先需要两个Stack（栈），其中一个应用于存放字符，另一个用于存放数字。

2.读到数字直接存入数字栈中，读到字符时，要咸鱼栈内前一元素（字符）进行比较，当当前（要存入的字符）优先级大于迁移字符时才存入，否则（>=）要仿佛将栈内元素弹出，并依次存入数字栈中。

提示：‘（' 的优先级默认比所有字符都小。所有字符都可以存在它后面；同时夜笔所有字符都大，可以存在所有字符后面

3.遇到 ‘）'时将栈内所有字符依次弹出，并存入数字栈中，知道遇到 ‘（' 为止

4.当所有字符、数字访问完毕时，栈内很可能还会有剩余的字符，这是将他们一次弹出，并纯如数字栈中

小技巧：

1.存放‘+'，‘-'时，如果只有当前一个数位空或者‘（' 时才进行存入操作，否则均弹出。

2.存放 ‘*'，‘/' 时，只有当前一个数位 ‘*'，‘/' 时才弹出其他情况下，均存入。

附上代码：

/*

* 中缀转后缀

*/

public void toPostfix() {

// TODO Auto-generated method stub

int sum = 0 ;//用于记入”（）“总个数

int j = 0 ;//用于读到”）“时循环出栈

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 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();

}

}

二、后缀wRSLRSsQww表达式计算

后缀表达式计算只遵循一个原则：

首先将表达式存在栈中

遇到符号时弹出两个相应的数字，进行计算后再次 存入栈内

最后栈内身下的唯一一个数，就是所要求的结果

/*

* 后缀表达式求值

*/

public String postfix() {

int a = 0 , b = 0;//栈中弹出的两数

int sum ;//求两数运算

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();

}

}

最后附上完整代码

//注：代码中有很多输出 方便读者实时查看运算过程中 各内容

// 这些输出导致篇幅较长 大家看明白后 删去即可

public class Calculate {

private Stack num; //后缀用栈 中转后数字栈

private Stack charnum;//中转后字符栈

private String []calculate;//存字符串数组

private int calculateLength;//字符串数组长度

public Calculate() {

// TODO Auto-generated constructor stub

num = new Stack<>(); //后缀用栈 中转后数字栈

charnum = new Stack<>();//中转后字符栈

calculate = new String[1000];//存字符串数组

calculateLength = 0 ;//字符串数组长度

}

//转字符串数组

public void toStringArray(String input) {

boolean pointFalg = false;

char charArray[] = input.toCharArray();

double number = 0;//用于导入多位数

int j = 0 ;//用于计入当前字符串数组的位数

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 ;//用于记入”（）“总个数

int j = 0 ;//用于读到”）“时循环出栈

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 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 ;//栈中弹出的两数

BigDecimal sum ;//求两数运算

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());

}

}

二、后缀直接输出

注意后缀表达式时

为了实现多位数运算，连续输入一串数时 ，输入完一个数加空格

如：要计算："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算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。