日常的に使用される代数式は中央の要素として表現さ​​れている (挿入辞). このデモでは、ほとんどの事業者ので、人間に理解できる (+, -, *, /) 二項演算子と2オペランド間彼らの部門が一緒にいる. しかしPCのための, このタイプの代数式の値を計算するためには、私たちがまだやるほど簡単ではありません. これを修正するには, プレフィックスまたはサフィックスの異なる型に元素から代数式の表現を転送するコンピュータ.

プレフィックス表現とは何ですか, 中置と接尾辞

ご想像の通り、上記の入門段落でどのように中置式, 単に演算子は2つのオペランドの間に配置されている, このコースは二重星である. 操作者の位置に基づいて, 我々は他のような代数式を実行できるかどうか? 答えは, と述べたように, 我々は3つの式の接頭辞を持っているとして (接頭辞), 挿入辞 (挿入辞) とサフィックス (接尾辞). それらをよりよく理解するために表現のプレフィックスとサフィックスを実行する方法について少し紹介を見てみましょう.

– 接頭辞: 表現プレフィックスは、オペランドの前にセットアップするオペレータによって表され. ポーランドの数学者ヤン·ウカシェヴィチによる名称「ポーランド記法」は年に発明の下でこのデモも知られている 1920. この表現に, 代わりに二次フォームファクタとしてX Yを書く, 私は XYを書きます. それらは異なる配置になる演算子の優先順位に応じて, あなたは、この導入の次のセクションでいくつかの例を見ることができます.

– 接尾辞: 接頭語とは対照的に, すなわち、オペレータは、オペランドの後に配置されます. このデモで「逆ポーランド記法」と呼ばれる、またはRPNと略記 (逆ポーランド表記法), 半ば十年に発明されました 1950 哲学者とコンピュータ科学者チャールズ·ハンブリンオーストラリアによる.

Một số ví dụ:

Postfixに中置式からメソッド変換

演算子の優先順位

計算を開始する前に、重要なことの一つは、への発現における演算子の優先順位でなければなりません. 簡単にするために、我々は唯一の二項演算を考慮し、通常含まれる: 掛ける (+),引く (-), 掛ける (*), 分割 (/). *演算子」によると、, / 「高い優先度を持ち、2つの演算子」, -". 演算子を次のようにこのように、我々は、優先モードをとっている:

public int priority(char c){		// thiet lap thu tu uu tien
		if (c == '+' || c == '-') return 1;
		else if (c == '*' || c == '/') return 2;
		else return 0;
	}

演算子とオペランドを確認してください

この変換アルゴリズムでは、文字列の構成要素は、演算子またはオペランドではないかどうかを確認する方法が必要です. 代わりに構造体を用いたのか、長いと不便な場合は、開発時に切り替える, 私がチェックするために正規表現を使用します.
また、入力文字列は、代数的表現であるため、, オペランドはAZおよびAZから数だけでなく、手紙を検討する必要があります.
一つのルールが1つだけの文字許される唯一の文字を使用する場合には、オペランドを表していることであるがあります, 複数桁の数字を使用することは一桁オペランドに組み合わせることができる場合であっても.

public boolean isOperator(char c){ 	// kiem tra xem co phai toan tu
		char operator[] = { '+', '-', '*', '/', ')', '(' };
		Arrays.sort(operator);
		if (Arrays.binarySearch(operator, c) > -1)
			return true;
		else return false;
	}

変換する前に、中置式を標準化

式は、余分な空白を入力することができます中置, 文字不適切またはスペルミス構文.
あなたのビューのこのセクション Javaで正規化された文字列

また、あなたは数の隣接桁をマージする必要が (オペランド), オペレーターの分離, 空間によって互いに分離され. これらの要素は、私は、トークンを呼ぶだろう.

public String[] processString(String sMath){ // xu ly bieu thuc nhap vao thanh cac phan tu
		String s1 = "", elementMath[] = null;
		InfixToPostfix  IFP = new InfixToPostfix();
		sMath = sMath.trim();
		sMath = sMath.replaceAll("\\s+"," "); //	chuan hoa sMath
		for (int i=0; i<sMath.length(); i++){
			char c = sMath.charAt(i);//sMath.substring(i,1);
			if (!IFP.isOperator(c))
				s1 = s1 + c;
			else s1 = s1 + " " + c + " ";
		}
		s1 = s1.trim();
		s1 = s1.replaceAll("\\s+"," "); //	chuan hoa s1
		elementMath = s1.split(" "); //tach s1 thanh cac phan tu
		//System.out.println(s1);
		return elementMath;
	}

ベテランプレフィックスに中置式を変換するためのアルゴリズム:

左から右に中置式の各トークンを読む, 各トークンで、私たちは、次の手順を実行する:
– オペランドの場合: 出力用.
– 「開き括弧の場合、(": 入力されたスタック
– 「閉じ括弧の場合)": 事業者は、「取り出して、あなたが開始括弧に達するまでスタック出力に入れ(". (括弧は、スタックから取り出されなければならない)
– オペレータの場合:
+/限りスタックの最上部に現在のオペレータに等しいか、超えた演算子と演算子の優先順位で、オペレータは、スタックおよび出力の外にそれを取った.
+/スタック上に現在の演算子を置く
すべて中置式を確認した後, スタックは、その場所にトークン要素をつかむし、出力をオンにする場合は、.

最高経営責任者（CEO: 私たちは、式Aを転送します* B C *((D-E)+F)/Postfixに中置フォームからG:

Javaをインストール

public String[] postfix(String[] elementMath){
		InfixToPostfix  IFP = new InfixToPostfix();
		String s1 = "", E[];
		Stack <String> S = new Stack <String>();
		for (int i=0; i<elementMath.length; i++){ 	// duyet cac phan tu
			char c = elementMath[i].charAt(0);	// c la ky tu dau tien cua moi phan tu

			if (!IFP.isOperator(c)) 		// neu c khong la toan tu
				s1 = s1 + " " + elementMath[i];		// xuat elem vao s1
			else{						// c la toan tu
				if (c == '(') S.push(elementMath[i]);	// c la "(" -> day phan tu vao Stack
				else{
					if (c == ')'){			// c la ")"
						char c1;		//duyet lai cac phan tu trong Stack
						do{
							c1 = S.peek().charAt(0);	// c1 la ky tu dau tien cua phan tu
							if (c1 != '(') s1 = s1 + " " + S.peek(); 	// trong khi c1 != "("
							S.pop();
						}while (c1 != '(');
					}
					else{
						while (!S.isEmpty() && IFP.priority(S.peek().charAt(0)) >= IFP.priority(c)){
						// Stack khong rong va trong khi phan tu trong Stack co do uu tien >= phan tu hien tai
							s1 = s1 + " " + S.peek();	// xuat phan tu trong Stack ra s1
							S.pop();
						}
						S.push(elementMath[i]); // 	dua phan tu hien tai vao Stack
					}
				}
			}
		}
		while (!S.isEmpty()){	// Neu Stack con phan tu thi day het vao s1
			s1 = s1 + " " + S.peek();
			S.pop();
		}
		E = s1.split(" ");	//	tach s1 thanh cac phan tu
		return E;
	}

そして最後に、メインプログラム:

public static void main(String[] agrs){
		String sMath, elementMath[] = null;
		InfixToPostfix  IFP = new InfixToPostfix();
		Scanner input = new Scanner(System.in);
		sMath = input.nextLine();					// 	nhap bieu thuc
		elementMath = IFP.processString(sMath);		//	tach bieu thuc thanh cac phan tu
		elementMath = IFP.postfix(elementMath);		// 	dua cac phan tu ve dang postfix
		for (int i=0; i<elementMath.length; i++)	// 	xuat dang postfix
			System.out.print(elementMath[i] + " ");
		input.close();
	}

結果が正しいかテストするには, 、オンライン変換サービスを使用することができ ここに . ウェブサイトでは、変換した後に式の値を計算し実行します.

ここから私たちは、構築することができます 表現の接尾辞の値を計算する