《java数据结构与算法》笔记-CH4-8栈结构实现后缀表达式计算结果

/**
* 中缀表达式转换成后缀表达式： 从输入（中缀表达式）中读取的字符，规则： 操作数： 写至输出 左括号： 推其入栈 右括号： 栈非空时重复以下步骤-->
* 若项不为(,则写至输出； 若项为(，则推出循环 operator(opThis): 若栈为空，推opThis； 否则，重复-->
* 弹出一项，若项为(,推其入栈； 若项为operator，且 若opTop<opThis,推入opTop,或 若opTop>=opThis,输出opTop,
* 若opTop<opThis则退出循环，或项为( 推入opThis 没有更多项： 当栈非空时，弹出项目，将其输出
*
*/
class StackI {
private int maxSize;
private char[] stack;
private int top;public StackI(int size) {
maxSize = size;
stack = new char[size];
top = -1;
}public void push(char value) {
stack[++top] = value;
}public char pop() {
return stack[top--];
}public char peek() {
return stack[top];
}public char peekN(int index) {
return stack[index];
}public int size() {
return top + 1;
}public boolean isFull() {
return top == maxSize;
}public boolean isEmpty() {
return top == -1;
}@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < size(); i++) {
sb.append(peekN(i) + ",");
}
sb.deleteCharAt(sb.length() - 1);
sb.append("]");
return sb.toString();
}public void display() {
System.out.print("当前栈: " + toString());
}
}class InToPost {
private String input, output;
private StackI stack;public InToPost(String in) {
input = in;
output = "";
int stackSize = input.length();
stack = new StackI(stackSize);
}public void gotOper(char opThis, int prec1) {
while (!stack.isEmpty()) {
char opTop = stack.pop();
if (opTop == '(') {
stack.push(opTop);
break;
} else {
int prec2;
if (opTop == '+' || opTop == '-')
prec2 = 1;
else
prec2 = 2;
if(prec2<prec1){
stack.push(opTop);
break;
}else{
output += opTop;
}
}
}
stack.push(opThis);
}public void gotParen(char ch){
while(!stack.isEmpty()){
char chx = stack.pop();
if(chx == '(')
break;
else
output += chx;
}
}public String doTrans() {
for (int i = 0; i < input.length(); i++) {
char ch = input.charAt(i);
switch (ch) {
case '+':
case '-':
gotOper(ch, 1);
break;
case '*':
case '/':
gotOper(ch, 2);
break;
case '(':
stack.push(ch);
break;
case ')':
gotParen(ch);
break;
default:
output += ch;
break;
}
}
while(!stack.isEmpty()){
output += stack.pop();
}
return output;
}
/**
* 计算后缀表达式结果
* 遇到操作数--入栈
* 遇到操作符--从栈中提取两个操作数，用操作符执行运算，结果入栈
* 注：这里转换后缀和计算后缀表达式共用了一个栈类型Model，所以在计算过程中字符和int转换时多了一些操作
* @param in
* @return
*/
public int doParse(String in){
stack = new StackI(20);
int num1,num2,result = 0;
int j;
char c;
for(j=0;j<in.length();j++){
c = in.charAt(j);
if(c>='0' && c<='9'){
stack.push(c);
}else{
num2 = (int)(stack.pop()-'0');
num1 = (int)(stack.pop()-'0');
switch (c) {
case '+':
result = num1+num2;
break;
case '-':
result = num1-num2;
break;
case '*':
result = num1*num2;
break;
case '/':
result = num1/num2;
break;
default:
result = 0;
break;
}
stack.push((char)(result+'0'));
}
}
result = (int)(stack.pop()-'0');
return result;
}
}public class InfixDemo {
/**
* 读取字符串
*
* @return
* @throws IOException
*/
public static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader reader = new BufferedReader(isr);
return reader.readLine();
}
public static void main(String[] args) throws IOException {
String input, output;
while(true){
System.out.println("enter:");
System.out.flush();
input = getString();
if(input.equals(""))
break;
InToPost i = new InToPost(input);
output = i.doTrans();
System.out.println(output);
System.out.println(i.doParse(output));
}
}
}