欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java实现中缀表达式转换为后缀表达式

程序员文章站 2024-01-24 11:30:16
...
实现中缀表达式转换为后缀表达式主要包含三个类,一个主函数,一个自定义栈的类,还有一个就是核心类,实现其转换。
一、自定义栈的类
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+/-