Java数据结构和算法中文第二版.pdf 代码
StackX.java
package com.ch4.infix;
public class StackX {
private int maxSize ;
private char[] stackArray ;
private int top ;
public StackX(int size){
maxSize = size ;
stackArray = new char[size] ;
top = -1 ;
}
public void push(char elem){
stackArray[++top] = elem ;
}
public char pop(){
return stackArray[top--] ;
}
public char peek(){
return stackArray[top] ;
}
public boolean isEmpty(){
return (top == -1) ;
}
public char peekIndex(int index){
return stackArray[index] ;
}
public int size(){
return top +1 ;
}
public void displayStack(String info){
System.out.print(info) ;
System.out.print("Stack (bottom -->top): ") ;
for (int j = 0; j < size(); j++){
System.out.print(peekIndex(j)) ;
System.out.print(' ');
}
System.out.println() ;
}
}
Infix.java
package com.ch4.infix;
public class Infix {
private StackX theStack;
private String input;
private String output = "";
public Infix() {
}
public Infix(String in) {
input = in;
int stackSize = input.length();
theStack = new StackX(stackSize);
}
public String doTrans() {
for (int i = 0; i < input.length(); i++) {
char ch = input.charAt(i);
if (ch == ' '){
continue ;
}
theStack.displayStack("For " + ch + " ");
switch (ch) {
case '+':
case '-':
gotOper(ch, 1);
break;
case '*':
case '/':
gotOper(ch, 2);
break;
case '(':
theStack.push(ch);
break;
case ')':
gotParent(ch);
break;
default:
output += ch;
break;
}
}
while (!theStack.isEmpty()) {
theStack.displayStack("While ");
output += theStack.pop();
}
theStack.displayStack("End ");
return output;
}
public void gotOper(char opThis, int prec1) {
while (!theStack.isEmpty()) {
char opTop = theStack.pop();
if (opTop == '(') {
theStack.push(opTop);
break;
} else {
int prec2 = 2;
if (opTop == '+' || opTop == '-') {
prec2 = 1;
}
if (prec2 < prec1) {
theStack.push(opTop);
break;
} else {
output += opTop;
}
} // end else
} // end while
theStack.push(opThis);
}
public void gotParent(char ch) {
while (!theStack.isEmpty()) {
char chx = theStack.pop();
if (chx == '(') {
break;
} else {
output += chx;
}
} // end while
}
}
InfixApp.java
package com.ch4.test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import com.ch4.infix.Infix;
public class InfixApp {
/**
* @param args
* @throws IOException
*/
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 ;
}
Infix theTrans = new Infix(input) ;
output = theTrans.doTrans() ;
System.out.println("src String : " + input) ;
System.out.println("Postfix is :" + output) ; ;
}
}
public static String getString() throws IOException{
InputStreamReader isr = new InputStreamReader(System.in) ;
BufferedReader br = new BufferedReader(isr) ;
String s = br.readLine() ;
return s ;
}
}