Infix to Postfix Convertor

uyfrjk · 发表于 2015-11-24 08:23:43

/**
* filename: InfixToPostfixConvertor.java
* package:
* author: Nick Ma
* email: nick.ma85@yahoo.com
* date: Nov 1, 2008
* description: this class implements a string convertor from infix to postfix.
*/
import java.util.*;
public class InfixToPostfixConvertor {
// Data Field
/** the operator stack */
private Stack<Character> operatorStack;
/** the operators */
private static final String OPERATORS = "+-*/()";
/** the precedence of the operators */
private static final int[] PRECEDENCE = {1, 1, 2, 2, -1, -1};
/** the postfix string */
private StringBuilder postfix;
/**
* description: the default constructor
*/
public InfixToPostfixConvertor() {
// TODO Auto-generated constructor stub
postfix = new StringBuilder();
}
/**
* description: convert a string from infix to postfix
* @param infix - the infix string to input
* @return - the postfix string
* @throws Exception
*/
public String convert(String infix) throws Exception {
operatorStack = new Stack<Character>();
StringTokenizer infixTokens = new StringTokenizer(infix);
try {
// process each token in the infix string
while(infixTokens.hasMoreTokens()) {
String nextToken = infixTokens.nextToken();
char firstChar = nextToken.charAt(0);
// determine if it is an operator
if(Character.isJavaIdentifierStart(firstChar)
|| Character.isDigit(firstChar)){
postfix.append(nextToken);
postfix.append(' ');
} else if(isOperator(firstChar)) {
processOperator(firstChar);
} else {
throw new SyntaxErrorException("syntax error!");
}
}
// pop any remaining operators and append them to postfix
while(!operatorStack.isEmpty()) {
Character op = operatorStack.pop();
// any '(' on the stack is not matched
if(op.charValue() == '(') {
throw new SyntaxErrorException("syntax error!");
}
postfix.append(op);
postfix.append(' ');
}
return postfix.toString();
} catch(EmptyStackException e) {
throw new SyntaxErrorException("the stack is empty!");
}
}
/**
* description: process operators
* @param op - the operator
*/
private void processOperator(char op) {
if(operatorStack.isEmpty() || op == '(') {
operatorStack.push(op);
} else {
// peek the operator stack
char topOp = operatorStack.peek().charValue();
if(precedence(op) > precedence(topOp)) {
operatorStack.push(op);
} else {
// pop all stacked operators with equal or higher precedence than op
while(!operatorStack.isEmpty() && precedence(op) <= precedence(topOp)) {
operatorStack.pop();
if(topOp == '(') {
break;
}
postfix.append(topOp);
postfix.append(' ');
if(!operatorStack.isEmpty()) {
// reset topOp
topOp = operatorStack.peek().charValue();
}
}
if(op != ')') {
operatorStack.push(op);
}
}
}
}
/**
* description: determine the precedence of an operator
* @param op - the operator
* @return - the precedence
*/
private int precedence(char op) {
return PRECEDENCE[OPERATORS.indexOf(op)];
}
/**
* description: determine whether a char is an operator
* @param op - the given char
* @return - true if the char is an operator
*/
private boolean isOperator(char op) {
return OPERATORS.indexOf(op) != -1;
}
// test function
public static void main(String[] args) {
InfixToPostfixConvertor pc = new InfixToPostfixConvertor();
try {
System.out.println(pc.convert("( x + y ) * ( ( a + b ) / c )"));
} catch(Exception e) {
e.printStackTrace();
}
}
}
/**
* filename: SyntaxErrorException.java
* package:
* author: Li Ma
* email: nick.ma85@yahoo.com
* date: Oct 3, 2008
* description: this exception shows a syntax error.
*/
public class SyntaxErrorException extends Exception {
private static final long serialVersionUID = 1L;
public SyntaxErrorException(final String message) {
super(message);
}
}

账号		自动登录	找回密码
密码			立即注册

VMware vcenter+vSphere 6.5 U2共享

【跟谁学】韩宇极简英语课-技术人员不得不

用Zabbix通过JMX方式监控weblogic

winhex数据恢复教程（非常巨大，内容丰富）

Symantec Backup Exec 2015 2016/2012 BE20

NetScaler VPX部署之：NetScaler Gateway调

zabbix3.4.1安装部署+微信推送信息+大屏显

[经验分享] Infix to Postfix Convertor

扫码加入运维网微信交流群