/**
* 使用栈存储后缀表达式
* Create by Administrator
* 2018/6/13 0013
* 下午 2:25
**/
public class StackX {
private int maxSize;
private char[] stackArray;
private int top;
public StackX(int size) // 构造函数
{
maxSize = size;
stackArray = new char[maxSize];
top = -1;
}
public void push(char j) // 将项目放在堆栈的顶部
{
stackArray[++top] = j;
}
public char pop() // 从堆栈顶部取项
{
return stackArray[top--];
}
public char peek() // 从堆栈顶部查看
{
return stackArray[top];
}
public boolean isEmpty() // 如果栈为空，则为true
{
return (top == -1);
}
public boolean isFull() // 如果堆栈已满 true
{
return (top == maxSize - 1);
}
public int size() // return size
{
return top + 1;
}
public char peekN(int n) // peek at index n
{
return stackArray[n];
}
public void displayStack(String s) {
System.out.print(s);
System.out.print("Stack (bottom-->top): ");
for (int j = 0; j < size(); j++) {
System.out.print(peekN(j));
System.out.print(' ');
}
System.out.println("");
}
}
/**
* 使用栈存储计算过程结果
* Create by Administrator
* 2018/6/14 0014
* 上午 10:37
**/
public class StackR {
private int maxSize;
private int[] stackArray;
private int top;
public StackR(int size) // 构造函数
{
maxSize = size;
stackArray = new int[maxSize];
top = -1;
}
public void push(int j) // 将项目放在堆栈的顶部
{
stackArray[++top] = j;
}
public int pop() // 从堆栈顶部取项
{
return stackArray[top--];
}
public int peek() // 从堆栈顶部查看
{
return stackArray[top];
}
public boolean isEmpty() // 如果栈为空，则为true
{
return (top == -1);
}
public boolean isFull() // 如果堆栈已满 true
{
return (top == maxSize - 1);
}
public int size() // return size
{
return top + 1;
}
public int peekN(int n) // peek at index n
{
return stackArray[n];
}
public void displayStack(String s) {
System.out.print(s);
System.out.print("Stack (bottom-->top): ");
for (int j = 0; j < size(); j++) {
System.out.print(peekN(j));
System.out.print(' ');
}
System.out.println("");
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* Create by Administrator
* 2018/6/13 0013
* 下午 2:38
**/
public class InTOPost {
private StackX stackX;
private StackR stackR;
private String input;
private String outPut = "";
public InTOPost(String in) {
this.input = in;
int stackSize = input.length();
stackX = new StackX(stackSize);
}
/**
* 中缀表达式转后缀表达式
* @return
*/
public String doTrans() {
for (int i = 0; i < input.length(); i++) {
char ch = input.charAt(i);//拿到每个字符
stackX.displayStack("For " + ch + " ");
switch (ch) {
case '+':
case '-':
getOpera(ch, 1);
break;
case '*':
case '/':
getOpera(ch, 2);
break;
case ')':
getParen(ch);
break;
case '(':
stackX.push(ch);
break;
default:
outPut = outPut + ch; //是数字将其写入输出
break;
}
}
while (!stackX.isEmpty()) {
stackX.displayStack("While ");
outPut = outPut + stackX.pop();
}
stackX.displayStack("End ");
return outPut;
}
private void getOpera(char opThis, int prec1) {
while (!stackX.isEmpty()) {
char opTop = stackX.pop();
if (opTop == '(') {
stackX.push(opTop);
break;
} else {
int prec2;
if (opTop == '+' || opTop == '-') {
prec2 = 1;
} else {
prec2 = 2;
}
if (prec2 < prec1) {
stackX.push(opTop);
break;
} else {
outPut = outPut + opTop;
}
}
}
stackX.push(opThis);
}
private void getParen(char ch) {
while (!stackX.isEmpty()) {
char chx = stackX.pop();
if (chx == '(') {
break;
} else {
outPut = outPut + chx;
}
}
}
/**
* 计算后缀表达式的结果
* @param output
* @return
*/
public int doParse(String output) {
stackR = new StackR(20); //新建堆栈
char ch;
int num1, num2, interAns;
for (int i = 0; i < output.length(); i++) { //遍历后缀表达式的字符串
ch = output.charAt(i); // 读取到每一个字符
stackR.displayStack(ch + " ");
if (ch >= '0' && ch <= '9') { // 判断是不是数字
stackR.push((int) (ch - '0')); // 放入到栈里
} else {
num2 = stackR.pop(); // 如果不是数字，就从栈里取出两个数字
num1 = stackR.pop();
switch (ch) { // 判断是哪个运算符，并计算
case '+':
interAns = num1 + num2;
break;
case '-':
interAns = num1 - num2;
break;
case '*':
interAns = num1 * num2;
break;
case '/':
interAns = num1 / num2;
break;
default:
interAns = 0;
}
stackR.push(interAns); // 把计算结果放入栈里
}
}
interAns = stackR.pop(); // 获得最终结果
return interAns;
}
/**
* 获取用户输入
* @return
* @throws IOException
*/
public static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
public static void main(String[] args) throws IOException {
String input, output;
while (true) {
System.out.print("Enter infix: ");
System.out.flush();
input = getString();
if (input.equals("")) {
break;
}
InTOPost toPost = new InTOPost(input);
output = toPost.doTrans();
System.out.println("Postfix is " + output + "\n");
int result = toPost.doParse(output);
System.out.println("结果：" + result);
}
}
运行测试：
请输入: (4+2*3)/2
For ( Stack (bottom-->top):
For 4 Stack (bottom-->top): (
For + Stack (bottom-->top): (
For 2 Stack (bottom-->top): ( +
For * Stack (bottom-->top): ( +
For 3 Stack (bottom-->top): ( + *
For ) Stack (bottom-->top): ( + *
For / Stack (bottom-->top):
For 2 Stack (bottom-->top): /
While Stack (bottom-->top): /
End Stack (bottom-->top):
Postfix is 423*+2/
4 Stack (bottom-->top):
2 Stack (bottom-->top): 4
3 Stack (bottom-->top): 4 2
* Stack (bottom-->top): 4 2 3
+ Stack (bottom-->top): 4 6
2 Stack (bottom-->top): 10
/ Stack (bottom-->top): 10 2
结果：5
