数据结构——栈的应用，中缀表达式转换为后缀表达式

更多精彩请到 http://www.139ya.com

转自: http://blog.chinaunix.net/u/16292/showart_490167.html

把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符，对于不同类型的字符按不情况进行处理。

加减运算符的优先级设定为1，乘除运算符的优先级设定为2，在栈中保存的特殊运算符’@’和’(’的优先级设定为0

1. 若遇到的是空格则认为是分隔符，不需要进行处理；
2. 若遇到的是数字或小数点，则直接写入到s2中，并在每个数值的最后写入一个空格；
3. 若遇到的是左括号，则应把它压入到运算符栈中，待以它开始的括号内的表达式转换完毕后再出栈；
4. 若遇到的是右括号，则表明括号内的中缀表达式已经扫描完毕，把从栈顶直到保存着的对应左括号之间的运算符依次退栈并写入s2串中；
5. 若遇到的是运算符，
5.1 当该运算符的优先级大于栈顶运算符的优先级时，表明该运算符的后一个运算对象还没有被扫描也没有被放入到s2串中，应把它暂存于运算符栈中，待它的后一个运算对象从s1串中读出并写入到s2串中后，再令其出栈并写入s2串中；
5.2 若遇到的运算符的优先级小于或等于栈顶运算符的优先级，这表明栈顶运算符的两个运算对象已经被保存到s2串中，应将栈顶运算符退栈并写入到s2串中，对于新的栈顶运算符仍继续进行比较和处理，直到被处理的运算符的优先级大于栈顶运算符的优先级为止，然后让该运算符进栈即可。
按照以上过程扫描到中缀表达式结束符’@’时，把栈中剩余的运算符依次退栈并写入到后缀表达式中，再向s2写入表达式结束符’@’和字符串结束符’{post.abstract}’，整个转换过程就处理完毕，在s2中就得到了转换成的后缀表达式。

下面是java源代码：

清单1：StackChar.java 栈


package zieckey.datastructure.study.stack;

public class StackChar
{
private int maxSize; // size of stack array

private char[] stackArray;
private int top; // top of stack


public StackChar( int maxSize )
{
this.maxSize = maxSize;// 设置数组大小

stackArray = new char[maxSize];// 创建数组

top = -1;// 还没有任何元素

}

public void push( char ch )
{// 入栈

if ( isFull() )
{
System.out.println( "Cannot insert item " + ch + "! The stack is full." );
} else
{
top++ ;
stackArray[top] = ch;
}
}

public char pop()
{// 出栈

if ( isEmpty() )
{
System.out.println( "The stack is empty." );
return 0;
} else
{
char ch = stackArray[top];
stackArray[top] = 0;
top-- ;
return ch;
}
}

public int size()
{
return top + 1;
}

public char peek()
{// 返回栈顶元素

return stackArray[top];
}

public char peekN( int n )
{// 返回index为n的元素

return stackArray[n];
}

public boolean isEmpty()
{
return ( -1 == top );
}

public boolean isFull()
{
return ( maxSize - 1 == top );
}

public void displayStack()
{
System.out.print( " Stack: " );
for ( int i = 0; i < precedencestack =" precedence(" precedencein =" precedence("> precedenceStack )
{
return 1;
} else if ( precedenceIn == precedenceStack )
{
return 0;
} else
{
return -1;
}
}

/**
* 计算传入参数的优先级
*
* @param ch
* @return
*/
public static int precedence( char ch )
{
if ( '+' == ch || '-' == ch )
{
return PrecedenceAdd;
} else if ( '*' == ch || '/' == ch )
{
return PrecedenceMultiply;
} else if ( '(' == ch )
{
return PrecedenceOpenParentheses;
} else if ( ')' == ch )
{
return PrecedenceCloseParentheses;
} else
{
return PrecedenceOthers;
}
}

private static final int PrecedenceAdd = 1;
private static final int PrecedenceMultiply = 2;
private static final int PrecedenceOpenParentheses = 0;
private static final int PrecedenceCloseParentheses = 3;
private static final int PrecedenceOthers = -1;
}


清单2：Infix2Postfix.java 中缀表达式转换为后缀表达式


package zieckey.datastructure.study.stack;

public class Infix2Postfix
{
private StackChar theStack;
private String input;
private String output = "";

public Infix2Postfix( String in ) // constructor

{
input = in;
int stackSize = input.length( );
theStack = new StackChar( stackSize/2 );
}

/**
* A*(B+C)-D/(E+F) The opThis operator has just been read from the infix
* input, while the opTop operator has just been popped off the stack.
*
* 加减运算符的优先级设定为1，乘除运算符的优先级设定为2，在栈中保存的运算符’(’的优先级设定为0
*
* 把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符，对于不同类型的字符按不情况进行处理。
*
* 处理方法步骤：
* 1. 若遇到的是操作数，则直接写入到s2中，并在每个数值的最后写入一个空格；
* 2. 若遇到的是左括号，则应把它压入到运算符栈中，待以它开始的括号内的表达式转换完毕后再出栈；
* 3. 若遇到的是右括号，则表明括号内的中缀表达式已经扫描完毕，把从栈顶直到保存着的对应左括号之间的运算符依次退栈并写入s2串中；
* 4. 若遇到的是运算符，
* 4.1 当该运算符的优先级大于栈顶运算符的优先级时，表明该运算符的后一个运算对象还没有被扫描也没有被放入到s2串中，
* 应把它暂存于运算符栈中，待它的后一个运算对象从s1串中读出并写入到s2串中后，再令其出栈并写入s2串中；
* 4.2 若遇到的运算符的优先级小于或等于栈顶运算符的优先级，这表明栈顶运算符的两个运算对象已经被保存到s2串中，
* 应将栈顶运算符退栈并写入到s2串中，对于新的栈顶运算符仍继续进行比较和处理，
* 直到被处理的运算符的优先级大于栈顶运算符的优先级或者栈为空时为止，然后让该运算符进栈即可。
*
*/
public String doTrans()
{
char ch;
int len = input.length( );
for ( int index = 0; index < ch =" input.charAt(" output =" output"> StackChar.precedence( theStack.peek( ) ) )
{
theStack.push( ch );
} else
{
/**
* 该运算符的优先级小于或等于栈顶运算符的优先级,应将栈顶运算符退栈并写入到输出字符串中，
* 对于新的栈顶运算符仍继续进行比较和处理，直到被处理的运算符的优先级大于栈顶运算符的优先级或者栈为空时为止，
* 然后让该运算符进栈即可。
*/
while ( !theStack.isEmpty( ) )
{
if ( StackChar.precedence( ch ) > StackChar.precedence( theStack.peek( ) ) )
{
break;
} else
{
output = output + theStack.pop( );
}
}
theStack.push( ch );
}
break;
case '(' :// 当其他运算符与之比较时优先级为0。当'('与其它运算符比较时优先级最高，直接入栈

theStack.push( ch );
break;
case ')' :// 优先级为3，为最高优先级，遇到后，对栈进行出栈操作

while ( !theStack.isEmpty( ) )
{
if ( '(' != theStack.peek( ))
{
output = output + theStack.pop( );
} else
{
theStack.pop( );
break;
}
}
break;
case ' ':
break;
default : // not an operator, must be an operand

output = output + ch;// write it into output

break;
}// end switch

}
}



清单3：Postfix.java 计算后缀表示式的值


package zieckey.datastructure.study.stack;

public class Postfix
{
private String inPostfix;
private StackX theStack;
private int size;

public Postfix( String a )
{
inPostfix = a;
size = inPostfix.length( );
theStack = new StackX(size);
}

/**
* 计算数据成员 inPostfix(为后缀表达式) 的值，
*
* 方法：
* 从左至右扫描后缀表达式，遇到运算数就将其压入栈内；
* 遇到运算符就做2次出栈操作，将操作数用这个运算符进行运算，将结果压入栈中。
* 知道扫描完，最后出栈操作就是表达式的最终计算结果。
*
* @return
*/
public double calculatePostfix()
{
char chRead;
for ( int i = 0; i < chread =" inPostfix.charAt(">='0'&&chRead<='9' ) { theStack.push( (int)(chRead-'0') ); } break; } } return theStack.pop( ); } private void disposeOperator( char chRead ) { double num1; double num2; double interAns = 0; num2 = theStack.pop( ); num1 = theStack.pop( ); switch ( chRead ) { case '+' : interAns = num1 + num2; break; case '-' : interAns = num1 - num2; break; case '*' : interAns = num1 * num2; break; case '/' : interAns = num1 / num2; break; default : break; } theStack.push( interAns ); } }

清单4：InfixCalcApp.java 测试程序main


package zieckey.datastructure.study.stack;

public class InfixCalcApp
{

/**
* @param args
*/
public static void main( String[] args )
{
// TODO Auto-generated method stub

String input = "5-(8+9-5*6)/3*(5+8-9)+6/(3+5-9-8+1)";
String output;
Infix2Postfix in2post = new Infix2Postfix( input );
Postfix postfix;
output = in2post.doTrans( );
postfix = new Postfix( output );
double ans = postfix.calculatePostfix( );
System.out.println( "Postfix is : " + output );
System.out.println( "The answer is : " + ans );

}

}



运行结果：

For 5 : Stack: 5
For - : Stack: 5
For ( : Stack: - 5
For 8 : Stack: -( 58
For + : Stack: -( 58
For 9 : Stack: -(+ 589
For - : Stack: -(+ 589+
For 5 : Stack: -(- 589+5
For * : Stack: -(- 589+5
For 6 : Stack: -(-* 589+56
For ) : Stack: -(-* 589+56*-
For / : Stack: - 589+56*-
For 3 : Stack: -/ 589+56*-3
For * : Stack: -/ 589+56*-3/
For ( : Stack: -* 589+56*-3/
For 5 : Stack: -*( 589+56*-3/5
For + : Stack: -*( 589+56*-3/5
For 8 : Stack: -*(+ 589+56*-3/58
For - : Stack: -*(+ 589+56*-3/58+
For 9 : Stack: -*(- 589+56*-3/58+9
For ) : Stack: -*(- 589+56*-3/58+9-
For + : Stack: -* 589+56*-3/58+9-*-
For 6 : Stack: + 589+56*-3/58+9-*-6
For / : Stack: + 589+56*-3/58+9-*-6
For ( : Stack: +/ 589+56*-3/58+9-*-6
For 3 : Stack: +/( 589+56*-3/58+9-*-63
For + : Stack: +/( 589+56*-3/58+9-*-63
For 5 : Stack: +/(+ 589+56*-3/58+9-*-635
For - : Stack: +/(+ 589+56*-3/58+9-*-635+
For 9 : Stack: +/(- 589+56*-3/58+9-*-635+9
For - : Stack: +/(- 589+56*-3/58+9-*-635+9-
For 8 : Stack: +/(- 589+56*-3/58+9-*-635+9-8
For + : Stack: +/(- 589+56*-3/58+9-*-635+9-8-
For 1 : Stack: +/(+ 589+56*-3/58+9-*-635+9-8-1
For ) : Stack: +/(+ 589+56*-3/58+9-*-635+9-8-1+
Postfix is : 589+56*-3/58+9-*-635+9-8-1+/+
The answer is : 21.583333333333332