来源:
维基百科-后缀表达式
目标
将中缀表达式转换为后缀表达式,比如((5 2) * (8-3))/4 转换为5 2 8 3 - * 4 /.
解题思路
将表达式的字符逐一处理,如果是数字(变量)则直接输出,如果是字符入栈,并按以下规则进行处理.
/-: 低优先级,所以将栈中的所有运算符出栈,之后将自己入栈.
*or/:高优先级,将栈中的其他乘除运算符出栈,之后将自己入栈.
(: 左括号则直接入栈.
): 右括号将栈中运算符逐一出栈,直到遇到左括号.
实现代码
代码语言：javascript复制/**
* solve the N-Queen problem
*/
public class NQueen {
//the number of chess board,example 8
private static final int N = 8;
// result, the result[i] mean: the location of [i] line is on result[i] column.
private int[] result = new int[N];
//total num of possible result
private int resultNum = 0;
/**
* calculation
*/
private void calculation(int n) {
//if n == N, print the result
if (n == N) {
for (int i = 0; i < result.length; i ) {
System.out.print(result[i] ",");
}
System.out.println();
resultNum ;
} else {
for (int i = 0; i < N; i ) {
// test every location possible
result[n] = i;
//if line n is allowed, locate the next line
if (isAllowed(n)) {
calculation(n 1);
}
}
}
}
/**
* judge current line is allowed or not.
*/
private boolean isAllowed(int i) {
// i is not allowed while it in same line or diagonal with the pre line
for (int j = 0; j < i; j ) {
if (result[i] == result[j] || Math.abs(i - j) == Math.abs(result[i] - result[j])) {
return false;
}
}
return true;
}
//main method, include some test cases
public static void main(String[] args) {
NQueen queen = new NQueen();
queen.calculation(0);
System.out.println(queen.resultNum);
}
}完。
ChangeLog
2019-02-24 完成
以上皆为个人所思所得，如有错误欢迎评论区指正。
欢迎转载，烦请署名并保留原文链接。
联系邮箱：huyanshi2580@gmail.com
