中缀式转后缀式工具类实现 - JAVA

*
*/
public final class SuffixExpressionUtils
{
/**
* 保存表达式中操作符的栈
*/
private static final Stack operators = new Stack();

/**
* 表达式的输出结果
*/
private static final StringBuilder result = new StringBuilder();

private static char lastElement;

/**
* 私有化构造方法，避免被实例化 <默认构造函数>
*/
private SuffixExpressionUtils()
{
}

/**
*
*


      * 把中缀式变后缀表达式
      * 
      * @param exp
      * @return
      *

*/
public static String getSuffixExp(String exp)
{
if (exp == null || exp.length() == 0)
{
return exp;
}

init();

// 所有{}[]全部替换成对应的小括号
exp = exp.replaceAll(Operators.OPEN_CURLY_BRACE, Operators.OPEN_BRACKET + Operators.EMPTY);
exp = exp.replaceAll(Operators.CLOSE_CURLY_BRACE, Operators.CLOSE_BRACKET + Operators.EMPTY);
exp = exp.replaceAll(Operators.OPEN_SQUARE_BRACKET, Operators.OPEN_BRACKET + Operators.EMPTY);
exp = exp.replaceAll(Operators.CLOSE_SQUARE_BRACKET, Operators.CLOSE_BRACKET + Operators.EMPTY);

// 去掉表达式中所有的" "
exp = exp.replaceAll(Operators.SPACE + Operators.EMPTY, Operators.EMPTY);

char[] characters = exp.toCharArray();

for (char ch : characters)
{
// 如果不是操作符，直接添加
if (!OperatorUtils.isOperator(ch))
{
addCharToResult(ch);
}
// 如果是')'，则从操作符栈中压出操作符，直到'('为止
else if (ch == Operators.CLOSE_BRACKET)
{
popUntilOpenBracket();
}
// 如果是'('或者操作符的优先级高于栈顶元素(如果栈顶时'('时，做特殊处理)
else if (ch == Operators.OPEN_BRACKET || !isLowerThanTop(ch))
{
operators.push(ch);
}
// 如果优先级不高于栈顶元素时，栈顶元素出栈，直到栈顶元素优先级高于待入栈元素，并把待入栈元素入栈
else

{
popUntilLowerTop(ch);
}
lastElement = ch;
}

popAllOperators();
return result.toString().trim();
}

/**
*
*


      * 由于定义的是静态方法，执行前，先清空操作符栈中的内容，避免受上一次的干扰
      * 
      *

*/
private static void init()
{
operators.clear();
result.delete(0, result.length());
}

/**
*
*


      * 碰到')'时，从操作符栈中弹出操作符，直到'('为止
      * 
      *

*/
private static void popUntilOpenBracket()
{
char lastElement = operators.lastElement();

while (lastElement != Operators.OPEN_BRACKET)
{
addCharToResult(operators.pop());
lastElement = operators.lastElement();
}

// 最后再弹出'('
operators.pop();
}

/**
*
*


      * 待入栈元素优先级是否不高于栈顶元素，栈为空时，为高于
      * 
      * @param ch
      * @return
      *

*/
private static boolean isLowerThanTop(char ch)
{
// 操作符栈为空或为'('时，操作符需要直接入栈
if (operators.isEmpty() || operators.lastElement() == Operators.OPEN_BRACKET)
{
return false;
}
char topChar = operators.lastElement();
return OperatorUtils.isLowerOfPriority(ch, topChar);
}

/**
*


      * 当待入栈的操作符优先级不高于栈顶时，栈顶元素出栈，直至栈顶元素低于待入栈元素，然后再把待入栈元素入栈
      * 
      * @param ch

中缀式转后缀式工具类实现 (三)