# 單元四 以遞迴解題

## 定義語言
### 文法 : 判斷合不合法
辨識語法，若不合法不能編譯。像是有沒有加分號，是否用了不合法的字元，變數是否用了保留字等。

## 以遞迴做迴文檢查

// PSEUDOCODE

isPal(in w: string):boolean
    if(w is the empty string or w is of length 1) return true;
    else if (w's first and last characters are the same letter)
        return isPal(w minus the first and last character);
    else return false;
    
//C++

 boolean isPal(string s){
     if(s.length()<=1) return true;
     else if(s[0]==s[s.length()-1]) return isPal(s.substr(1,s.length()-2));     
     else return false;
 }

## 算數運算式
以A+B為例子(此為中序)
前序:+AB
後序:AB+
中序的問題:有加減乘除的順序問題，還有括號的問題(像是括號少了一個)。
:::success
轉成前序或後序可以降低文法的複雜度、沒有優先順序的問題、沒有括號。
:::

### 以下是中序轉後序的算式:

// c++ 11
// 將中序運算的字串轉成後續運算的LinkedList 
// 配合上一章的LinkedList
LinkedList<string> toPostfixExpression(string str) {
	// vector<string> v;
	LinkedList<string> list; // 即將被回傳的list 
	stringstream ss; // 用來組合出數字的stringstream 
	Stack<char> op; // 用來暫存operator的Stack 
	// iterate over all char in str
	for(char c : str) {
		if(c== ' '|| c == '\t' || c == '\n' ) continue; // 如果是空白字元 就跳過 
		// 如果是數字的話 
		if(c>='0'&&c<='9') {
			ss<<c; // 將c推進去ss
		} 
		// 如果是左括號的話 
		else if (c=='(') {
			op.push(c); // 把左括號push進stack 
		}
		// 如果是右括號的話 
		 else if (c == ')') {
		 	// 如果ss的長度不等於0 就代表有數字 因此要把數字推進去list裡面 
			if(ss.str().length()) {
				list.push(ss.str());
				// 清空 
				ss.str("");
				ss.clear();
			}
			// 要是存operator的Stack不是空的話 且存在最上層的不是左括號的話 
			while(!op.isEmpty()&&op.peek()!='(') {
				
				list.push(string(1,op.pop()));
			}
			if(!op.isEmpty())op.pop();
		} else if (c == '+' || c == '-' || c == '*' || c == '/') {
			
			if(ss.str().length()!=0) {
				list.push(ss.str());
				ss.str("");
				ss.clear();
			}
			while(!op.isEmpty()&&op.peek()!='('&&getPriority(op.peek())>=getPriority(c)) {
				list.push(string(1,op.pop()));
			}
			op.push(c);
		}
	}
	if(ss.str().length()) {
		list.push(ss.str());
		ss.str("");
		ss.clear();
	}
	while(!op.isEmpty()) {
		if(op.peek()=='(') op.pop();
		else list.push(string(1,op.pop()));
	}
	return list;
}

### 以下是前序轉後序的偽代碼:

// PSEUDOCODE
convert(inout pre:string out post:string)
    ch = first character in pre;
    Delete first character in pre;
    if( ch is a lowercase letter) post = post + ch;
    else{
        convert(pre,post);
        convert(pre,post);
        post = post + ch;
    }

## 八皇后問題
:::success
定義 :
放八個皇后，並且不會互相攻擊。
棋盤 : 8 * 8格
每個皇后有8個攻擊方向
**40億種方法***
:::

方法 : 一直往下找，遇到死路就退回去上一層，這就是Backtracking最基本的概念

### 可以利用遞迴解決這個問題
> base case : 8個填滿
> 遞迴呼叫 : 如果成功將皇后放下 就遞迴下去放另外一欄
> 若無法放 : **必須Backtrack**