Java中缀表达式转后缀表达式实现方法详解
这篇文章主要介绍了Java中缀表达式转后缀表达式实现方法,结合实例形式分析了Java中缀表达式转换成后缀表达式的相关算法原理与具体实现技巧,需要的朋友可以参考下本文实例讲述了java中缀表达式转后缀表达式实现方法。分享给大家供大家参考，具体如下：
本文先给出思路与方法，最后将给出完整代码
算法综述：
一、中缀表达式转后缀表达式：
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.equals("(")) {
charnum.push(calculate);
sum ++ ;
}else if ( calculate.equals(")") ) {
outstack = charnum.pop();//进入前先出一个
while ( !outstack.equals("(") ){
num.push(outstack);
outstack = charnum.pop();
}//最后一次outstack正好接到”（“不入栈
sum ++ ;
}else if (calculate.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.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.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.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);
}
}
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 = zanshi.pop();
}
}
二、后缀表达式计算
后缀表达式计算只遵循一个原则：
首先将表达式存在栈中
遇到符号时弹出两个相应的数字，进行计算后再次 存入栈内
最后栈内身下的唯一一个数，就是所要求的结果
/*
* 后缀表达式求值
*/
public string postfix() {
int a = 0 , b = 0;//栈中弹出的两数
int sum ;//求两数运算
for (int i = 0; i < calculatelength ; i++ ) {
if (i == 0) {
num.push(calculate);
}else if (calculate.equals("+") ) {
b = integer.parseint(num.pop());
a = integer.parseint(num.pop());
sum = a + b ;
num.push(string.valueof(sum));
}else if (calculate.equals("-") ) {
b = integer.parseint(num.pop());
a = integer.parseint(num.pop());
sum = a - b ;
num.push(string.valueof(sum));
}else if (calculate.equals("*") ) {
b = integer.parseint(num.pop());
a = integer.parseint(num.pop());
sum = a * b ;
num.push(string.valueof(sum));
}else if (calculate.equals("/") ) {
b = integer.parseint(num.pop());
a = integer.parseint(num.pop());
sum = a / b ;
num.push(string.valueof(sum));
}else if (calculate.equals("%") ) {
b = integer.parseint(num.pop());
a = integer.parseint(num.pop());
sum = a / b ;
num.push(string.valueof(sum));
}else {
num.push(calculate);
}
}
return num.pop();
}
}
最后附上完整代码
//注：代码中有很多输出 方便读者实时查看运算过程中 各内容
// 这些输出导致篇幅较长 大家看明白后 删去即可
public class calculate {
private stack<string> num; //后缀用栈 中转后数字栈
private stack<string> charnum;//中转后字符栈
private string []calculate;//存字符串数组
private int calculatelength;//字符串数组长度
public calculate() {
// todo auto-generated constructor stub
num = new stack<>(); //后缀用栈 中转后数字栈
charnum = new stack<>();//中转后字符栈
calculate = new string;//存字符串数组
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 == '('){
calculate = "(";
}else if(chararray == ')'){
calculate = ")";
}else if (chararray == '+') {
calculate = "+";
}else if (chararray == '-') {
calculate = "-";
}else if (chararray == '*') {
calculate = "*";
}else if (chararray == '/') {
calculate = "/";
}else if (chararray == '%') {
calculate = "%";
}else if (chararray == '#') {
calculate = "#";
}else if (chararray == '.') {
system.out.println("find new . :");
pointbelow = 1;
// sizeofarray -- ;
pointfalg = true;
}else {
string str=string.valueof(chararray);
if (pointfalg == false) {
system.out.println("1:" + number);
number = number * 10 + double.parsedouble(str);
}else {
system.out.println("2:" + chararray);
number = number + double.parsedouble(str) * math.pow(0.1, pointbelow);
}
system.out.println("3:" + number + "i==" + i);
if( (i + 1) == sizeofarray ||( chararray < '0' || chararray > '9' ) && chararray != '.'){
if ( (i + 1) != sizeofarray && chararray == ' ') {
i++;
}
calculate = string.valueof(number);
system.out.println("number:" + number);
number = 0 ;
pointfalg = false;
}
}
system.out.println("---z->" + calculate);
}
calculatelength = j-- ;//不--会将‘#'存入
}
public void outputcalculate() {
for(int i = 0 ; i < calculatelength ; i ++ ){
system.out.println(calculate);
}
}
public void calculatetozero() {
for(int i = 0 ; i < calculatelength ; i ++ ){
calculate= calculate ;
}
}
//中缀转后缀
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);//-----------------------------
if ( calculate.equals("(")) {
charnum.push(calculate);
system.out.println("1-1 charpush " + calculate);//-----------------------------
sum ++ ;
}else if ( calculate.equals(")") ) {
system.out.println("2-1 charpush " + calculate);//-----------------------------
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.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.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.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.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.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);
num.push(calculate);
}
}
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 = zanshi.pop();
}
system.out.println("over ~~~~~2 ");
for(int i = 0 ; i < calculatelength ;i ++ ){
system.out.println(calculate);
}
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);
if (i == 0) {
num.push(calculate);
}else if (calculate.equals("+") ) {
b = new bigdecimal(num.pop());
a = new bigdecimal(num.pop());
sum = a.add(b) ;
num.push(string.valueof(sum));
}else if (calculate.equals("-") ) {
b = new bigdecimal(num.pop());
a = new bigdecimal(num.pop());
sum = a.subtract(b) ;
num.push(string.valueof(sum));
}else if (calculate.equals("*") ) {
b = new bigdecimal(num.pop());
a = new bigdecimal(num.pop());
sum = a.multiply(b) ;
num.push(string.valueof(sum));
}else if (calculate.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.equals("%") ) {
b = new bigdecimal(num.pop());
a = new bigdecimal(num.pop());
sum = a.divideandremainder(b) ;
num.push(string.valueof(sum));
}else {
num.push(calculate);
}
}
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程序设计有所帮助。
原文链接：https://blog.csdn.net/qq_43377749/article/details/84483862
http://www.zzvips.com/article/178556.html
页:
[1]