Java实现中缀表达式转换为后缀表达式
程序员文章站
2024-01-24 11:30:16
...
实现中缀表达式转换为后缀表达式主要包含三个类,一个主函数,一个自定义栈的类,还有一个就是核心类,实现其转换。
一、自定义栈的类
二、核心实现类
三、主类代码
输入的表达式为:A*(B+C)-D/(E+F)
执行的结果如下:
请输入算术表达式:
A*(B+C)-D/(E+F)
for A Stack (bottom-->top):
for * Stack (bottom-->top):
for ( Stack (bottom-->top): *
for B Stack (bottom-->top): * (
for + Stack (bottom-->top): * (
for C Stack (bottom-->top): * ( +
for ) Stack (bottom-->top): * ( +
for - Stack (bottom-->top): *
for D Stack (bottom-->top): -
for / Stack (bottom-->top): -
for ( Stack (bottom-->top): - /
for E Stack (bottom-->top): - / (
for + Stack (bottom-->top): - / (
for F Stack (bottom-->top): - / ( +
for ) Stack (bottom-->top): - / ( +
While Stack (bottom-->top): - /
While Stack (bottom-->top): -
end while!! Stack (bottom-->top):
Profix is ABC+*DEF+/-
一、自定义栈的类
package date0617; /** *@author TonyJ *@time 2011-6-17 下午02:24:47 */ public class MyStack { private int maxSize;//栈的最大容量 private char[] ch; //栈的数据 private int top; //栈头标记 public MyStack(int s) { maxSize = s; ch = new char[s]; top = -1; } public void push(char c) {//入栈 ch[++top] = c; } public char pop() {//出栈 return ch[top--]; } public char peek() { return ch[top]; } public boolean isEmpty() { return top == -1; } public boolean isFull() { return top == (maxSize - 1); } public int size() { return top + 1; } public char get(int index) { return ch[index]; } public void display(String str) { System.out.print(str); System.out.print(" Stack (bottom-->top): "); for (int i = 0; i < size(); i++) { System.out.print(get(i)+" "); } System.out.println(); } }
二、核心实现类
package date0617; /** *@author TonyJ *@time 2011-6-17 下午02:43:48 */ public class InToPost { private MyStack ms;//自定义栈 private String input;//输入中缀表达式 private String output="";//输出的后缀表达式 public InToPost(String input) { this.input = input; int size = input.length(); ms = new MyStack(size); } public String doTrans() {//转换为后缀表达式方法 for (int i = 0; i < input.length(); i++) { char ch = input.charAt(i); ms.display("for " + ch + " "); switch (ch) { case '+': case '-': getOper(ch, 1); break; case '*': case '/': getOper(ch, 2); break; case '(': ms.push(ch); break; case ')': getParent(ch); break; default: output = output + ch; break; }//end switch }//end for while(!ms.isEmpty()){ ms.display("While "); output=output+ms.pop(); } ms.display("end while!!"); return output; } /** * @param ch * 获得上一级字符串 */ public void getParent(char ch) { while(!ms.isEmpty()){ char chx=ms.pop(); if(chx=='('){ break; }else{ output=output+chx; } } } /** * @param ch 操作符 * @param prec1 操作符的优先级 * 根据操作符的优先级判断是否入栈,及入栈的顺序 */ public void getOper(char ch, int prec1) { while (!ms.isEmpty()) {//判断栈是否为空 char operTop = ms.pop(); if (operTop == '(') { ms.push(operTop); break; } else { int prec2; if (operTop == '+' || operTop == '-') { prec2 = 1; } else { prec2 = 2; } if (prec2 <prec1) { ms.push(operTop); break; } else { output = output + operTop; } } }// end while ms.push(ch); } }
三、主类代码
package date0617; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** *@author TonyJ *@time 2011-6-17 下午03:44:49 */ public class InfixMain { public static void main(String[] args) { String input, output; while (true) { input = getString(); if ("".equals(input) || input == null) { break; } InToPost itp = new InToPost(input); output = itp.doTrans(); System.out.println("Profix is " + output + "\n"); } } public static String getString() { String output = ""; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); try { System.out.println("请输入算术表达式:"); output = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return output; } }
输入的表达式为:A*(B+C)-D/(E+F)
执行的结果如下:
请输入算术表达式:
A*(B+C)-D/(E+F)
for A Stack (bottom-->top):
for * Stack (bottom-->top):
for ( Stack (bottom-->top): *
for B Stack (bottom-->top): * (
for + Stack (bottom-->top): * (
for C Stack (bottom-->top): * ( +
for ) Stack (bottom-->top): * ( +
for - Stack (bottom-->top): *
for D Stack (bottom-->top): -
for / Stack (bottom-->top): -
for ( Stack (bottom-->top): - /
for E Stack (bottom-->top): - / (
for + Stack (bottom-->top): - / (
for F Stack (bottom-->top): - / ( +
for ) Stack (bottom-->top): - / ( +
While Stack (bottom-->top): - /
While Stack (bottom-->top): -
end while!! Stack (bottom-->top):
Profix is ABC+*DEF+/-