Algoritma dan contoh menghuraikan empat ungkapan aritmetik dalam kemahiran javascript_javascript

Apabila menulis kod, kadangkala kita menghadapi situasi di mana kita perlu menghuraikan sendiri empat ungkapan aritmetik Artikel ini memperkenalkan secara ringkas penggunaan JavaScript untuk menghuraikan empat ungkapan aritmetik mudah.

1. Konsep biasa

Notasi infiks (atau notasi infiks) ialah kaedah umum untuk menyatakan formula aritmetik atau logik Operator berada di tengah-tengah operan dalam bentuk infiks (contoh: 3 4). Iaitu, ungkapan aritmetik kami yang paling biasa digunakan, ungkapan infiks lebih mudah difahami oleh manusia, tetapi tidak mudah untuk dihuraikan oleh komputer.

Notasi Poland songsang (notasi Poland songsang, RPN, atau notasi Poland songsang) ialah kaedah ungkapan matematik yang diperkenalkan oleh ahli matematik Poland Jan Vukasiewicz pada tahun 1920. Dalam notasi Poland songsang, semua operator diletakkan selepas operan , jadi ia juga dipanggil tatatanda akhiran. Notasi Poland terbalik tidak memerlukan kurungan untuk menunjukkan keutamaan operator. Notasi Poland songsang memudahkan anda menggunakan struktur tindanan untuk menghuraikan dan mengira ungkapan Oleh itu, di sini kita menghuraikan empat ungkapan elemen dengan terlebih dahulu menukar ungkapan infiks kepada ungkapan Poland terbalik. Kemudian hitung nilainya.

2. Proses penukaran

Tukar ungkapan infix kepada ungkapan postfix (algoritma medan penjadualan)

1. Tanda muncul dalam baris gilir input
2. Jika token ialah nombor, tambahkannya pada baris gilir output
3. Jika ia adalah operator (-*/), bandingkan dengan operator di bahagian atas tindanan output Jika keutamaan adalah kurang daripada atau sama dengan operator di bahagian atas tindanan, letakkan operator di atas daripada tindanan dan tambahkannya pada baris gilir keluaran ( Gelung sehingga syarat di atas tidak dipenuhi), dan akhirnya tolak operator ini ke tindanan.
4. Jika ia tanda kurungan kiri, tolaknya pada tindanan
5. Jika ia adalah kurungan kanan, teruskan pop pengendali dari tindanan dan tambahkannya pada baris gilir keluaran sehingga elemen di bahagian atas tindanan ialah kurungan kiri. Pop kurungan kiri dan jangan tambahkannya pada baris gilir output. Jika kurungan kiri tidak ditemui, ini bermakna kurungan dalam ungkapan asal tidak simetri dan terdapat ralat.
6. Jika baris gilir input kosong dan masih terdapat operator pada tindanan, jika operator di atas tindanan adalah kurungan kiri, ini bermakna ungkapan asal mempunyai kurungan yang tidak sepadan. Pop operator dari timbunan satu demi satu dan tambahkannya pada baris gilir output.
7. Lengkapkan

3. Pelaksanaan penukaran kod

function isOperator(value){
	var operatorString = "+-*/()";
	return operatorString.indexOf(value) > -1
}

function getPrioraty(value){
	switch(value){
		case '+':
		case '-':
			return 1;
		case '*':
		case '/':
			return 2;
		default:
			return 0;
	}
}

function prioraty(o1, o2){
	return getPrioraty(o1) <= getPrioraty(o2);
}

function dal2Rpn(exp){
	var inputStack = [];
	var outputStack = [];
	var outputQueue = [];

	for(var i = 0, len = exp.length; i < len; i++){
		var cur = exp[i];
		if(cur != ' ' ){
			inputStack.push(cur);
		}
	}
	console.log('step one');
	while(inputStack.length > 0){
		var cur = inputStack.shift();
		if(isOperator(cur)){
			if(cur == '('){
				outputStack.push(cur);
			}else if(cur == ')'){
				var po = outputStack.pop();
				while(po != '(' && outputStack.length > 0){
					outputQueue.push(po);
					po = outputStack.pop();
				}
				if(po != '('){
					throw "error: unmatched ()";
				}
			}else{
				while(prioraty(cur, outputStack[outputStack.length - 1]) && outputStack.length > 0){
					outputQueue.push(outputStack.pop());
				}
				outputStack.push(cur);
			}
		}else{
			outputQueue.push(new Number(cur));
		}
	}
	console.log('step two');
	if(outputStack.length > 0){
		if(outputStack[outputStack.length - 1] == ')' || outputStack[outputStack.length - 1] == '('){
			throw "error: unmatched ()";
		}
		while(outputStack.length > 0){
			outputQueue.push(outputStack.pop());
		}
	}
	console.log('step three');
	return outputQueue;

}

console.log(dal2Rpn('1 + 2'));
console.log(dal2Rpn('1 + 2 + 3'));
console.log(dal2Rpn('1 + 2 * 3'));
console.log(dal2Rpn('1 + 2 * 3 - 4 / 5'));
console.log(dal2Rpn('( 1 + 2 )'));

console.log(dal2Rpn('( 1 + 2 ) * ( 3 - 4 ) / 5'));
console.log(dal2Rpn('( 1 + 2 ) * (( 3 - 4 ) / 5)'));

4. Penilaian ungkapan Poland terbalik

1. Paparkan token daripada baris gilir input
2. Jika ia adalah operan, tambahkannya pada tindanan output
3. Jika ia adalah operator, keluarkan kedua-dua operan daripada tindanan output dan lakukan pengiraan, dan tolak nilai yang dikira ke tindanan output.
4. Operasi gelung, jika baris gilir input kosong dan timbunan output hanya mempunyai satu nombor, nombor ini adalah hasilnya, jika tidak terdapat operan berlebihan.

5. Kod pengiraan

function evalRpn(rpnQueue){
	var outputStack = [];
	while(rpnQueue.length > 0){
		var cur = rpnQueue.shift();

		if(!isOperator(cur)){
			outputStack.push(cur);
		}else{
			if(outputStack.length < 2){
				throw "unvalid stack length";
			}
			var sec = outputStack.pop();
			var fir = outputStack.pop();

			outputStack.push(getResult(fir, sec, cur));
		}
	}

	if(outputStack.length != 1){
		throw "unvalid expression";
	}else{
		return outputStack[0];
	}
}

6. Kesimpulan

Notasi Poland songsang bukanlah sesuatu yang biasa anda lakukan apabila anda mula bersentuhan dengannya, tetapi selepas anda membiasakannya, anda akan mendapati bahawa idea itu sebenarnya sangat mudah, tidak seperti notasi infiks, yang mempunyai pelbagai keutamaan dan Kelas, logiknya sangat menyusahkan, tetapi notasi Poland terbalik adalah lebih ringkas, tidak perlu mengambil kira keutamaan sama sekali, dan tidak perlu tanda kurungan, kurungan persegi dan kurungan kerinting untuk mengganggu keadaan.