FantasyWorld

主要是利用堆疊的先進後出的特性來計算

如 A - B / C + ( D * E ) - F
轉成後置式的話為A B C / - D E * + F -
至於怎麼轉呢.. 直覺吧 反正就是要算的 放到右邊?
課本是用括號 滿麻煩的
像是
A - B / C + (D * E ) - F
A - (B / C) + (D * E) - F
A ( B C / ) - ( D E * ) + F -
A B C / - D E * + F -
轉成後置式後可以方便使用堆疊來計算結果
規則為 :
1.遇到運算子(+ - * / ...)就從堆疊提兩個運算元出來計算
2.遇到運算元 就存入堆疊裡

A B C / - D E * + F - 程式實際載跑的話是
A ---->存入堆疊
B ---->存入堆疊
C ---->存入堆疊
/ ----->遇到運算子了 從前面取出兩個 (Stack.pop() 兩次) 即 B C
再將 B / C 的結果 ---->存入堆疊
繼續....
- ----->遇到運算子 從前面取出兩個 即 A 還有 B/C的結果
再將 A-(B/C) 存入堆疊
.
.
.
一直計算到最後
所以是相當容易的，不需要擔心括號或是四則運算的規則

/*
	使用堆疊實作四則運算
*/
import java.util.Scanner;
public class Main{

    public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		System.out.print("請輸入算式 : ");
		while(input.hasNext())
		{
			Operation.compute(input.next());
			System.out.print("請輸入算式 : ");
		}
    }
}
class Operation
{
	public static void compute(String str)//將後置式進行運算
	{
		Stack s = new Stack(str.length());
		String [] data =transfer(str);//傳入轉換的方法得到後置式的分割陣列
		String ans = "";
		for(int i = 0 ; i < data.length ; i++)//讀出後置式的各個運算元運算子來做計算
		{
			if(data[i] == null)break;
//是運算子時
		if(data[i].equals("+")||data[i].equals("-")||data[i].equals("*")||data[i].equals("/")||data[i].equals("^"))
			{
				int b = Integer.parseInt(s.pop());//提出前面兩個儲存的值計算
				int a = Integer.parseInt(s.pop());
				if(data[i].equals("+"))
					s.push(""+(a+b));
				else if(data[i].equals("-"))
					s.push(""+(a-b));
				else if(data[i].equals("*"))
					s.push(""+(a*b));
				else if(data[i].equals("/"))
					s.push(""+(a/b));
				else if(data[i].equals("^"))
					s.push(""+(int)(Math.pow(a,b)));
			}
			else//是運算元時存入堆疊
				s.push(data[i]);

		}
		System.out.println("答案為 : "+s.pop());
	}
	public static String [] transfer(String data)//轉換成後置式
	{
		Stack s = new Stack(data.length());
		int index = 0;//為了將輸入的字串分割成陣列儲存用的索引值
		String [] ans = new String[data.length()];
		for(int i = 0 ; i < data.length() ;i++)
		{
			String opr = returnSplit(data,i);//傳入分割方法取得各個運算元或運算子
			if(opr.length() > 1)i+= (opr.length()-1);//避免傳出的是兩位數以上I未對應
//是運算子的話看其優先順序 是疊入還是取出
		if(opr.equals("+")||opr.equals("-")||opr.equals("*")||opr.equals("/")||opr.equals("^"))
			{
				while(s.index != -1 && priority(opr) <= priority(s.peep()))
				{
					ans[index++] = s.pop();
				}
				s.push(opr);
			}
			else if(opr.equals("("))
			{
				s.push(opr);
			}
			else if(opr.equals(")"))//取出運算子直到對應到"("以後
			{
				String tempS ="";
				while(s.index!= -1 &&!( (tempS = s.pop()).equals("(")) )
				{
					ans[index++] = tempS;
				}
			}
			else
			{
				ans[index++] =opr;
			}
		}
		while(s.index!=-1)ans[index++] = s.pop();
		return ans;
	}
	public static String returnSplit(String data,int index)//傳回分割後的值
	{
		String thisString ="";
		String s = String.valueOf(data.charAt(index));

		if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")||s.equals("(")||s.equals(")")||s.equals("^"))
		{
			return s;//直接傳回運算子
		}
		else
		{
			do{
				thisString += s;
				if(index+1 ==data.length())break;
				s = String.valueOf(data.charAt(++index));//後面的位數式運算元就累加
			}while(!s.equals("+")&&!s.equals("-")&&!s.equals("*")&&!s.equals("/")&&!s.equals("(")&&!s.equals(")")&&!s.equals("^"));
			return thisString;
		}
	}
	public static int priority(String opr)//運算子的優先順序
	{
		if(opr.equals("^"))return 3;
		else if(opr.equals("*")||opr.equals("/"))return 2;
		else if(opr.equals("+")||opr.equals("-"))return 1;
		else return 0;
	}
}
class Stack
{
	String [] stack;
	public int index;
	Stack(int max)
	{
		index = -1; //無元素
		stack = new String[max];
	}
	public void push(String data)
	{
		stack[++index] = data;
	}
	public String pop()
	{
		return stack[index--];
	}
	public String peep()
	{
		return stack[index];
	}
}