調度場演演算法(2018/09/10更)
然後以前忘記提
除非是只寫HTML的編輯器不然存檔時要注意這兩處一個是副檔名.html或.htm另一個是存檔類型改為所有文件或在一些編輯器中改成Hypertext文件
我很久沒寫程式了
這道題目以前就卡在這邊要是沒解決我覺得我的心理障礙會沒辦法突破因此還是回來雖然隱約覺得自己其實沒那麼想處理這題不過還是試試看吧!!最近回去玩軒轅劍壹、仙劍DOS版重拾了些回憶覺得還是回來再嘗試下好了雖說我清潔隊的工作其實目前的力氣還是不太能勝任的
(伏地挺身雖然可以30~40下左右(引體向上一陣子沒做,估計大概還是只能一兩下,出力部位問題),但是碰到像是較傳統、老式、比人高一些的電冰箱,可能有70公斤的還是連固定支點翻都有困難,有些比較重的垃圾包也甩不上垃圾車,嗯,由於不是重點就先在此打住)調度場演演算法在處理什麼問題呢?一個算式在我們眼中看來是 1+1=2若僅是這樣
還可以用暫存器(寄存器),累加器(accumulator),算數邏輯單元(ALU)來處理但式子若稍微複雜、形式不固定些對於電腦來說這樣的式子是很難處理的其實這種程序要怎麼寫維基百科已經給出答案了我實際測試了下也可行不過現在要改用Javascript來寫此外我那只是複製源碼貼上測試確認可行其實我還是不會的因此還是要回歸原點
一開始先處理最簡單的狀況3+2改寫成32+這樣運算時只要字串由左邊讀到右邊碰上運算符號再讀兩個最鄰近數值就能得出答案 3(左1第一個數值)+2(左2第二個數值)=5嗯,加法這舉例不太好因為具有交換性那稍微複雜些的話
3-2*4先寫答案324*-還原就我想的至少有兩步驟2*4 = 83 - (2*4) = 3 - 8 = -5先做到這邊就好括弧與小數點跟冪(次方)那我去思考下!!這步驟主要是要比對各運算符號(就是運運算元,operator)的優先權理論上做到這邊應該不難才對
做著做著發現有個問題那就是維基百科上的調度演演算法是示意的數值是用其實是變數__1或$1這些來表達實際上有些細節要自行處理例如當數值二位數以上時（也就是並非個位數或有負數與小數的問題C語言我印象中用預設函式庫處理這類問題挺費事的好在這點在使用Javascript上比較好解決印象中啦!好不好解決晚些就知道）
JavaScript的處理最簡單狀況的話，源碼大概也要這樣才能達成
而且這還是沒算出答案的狀況我等等要先處理算出答案的狀況(估計是用switch-case處理運算符號與文字數值轉換)我英文很破僅供參考！<!DOCTYPE html>
<meta charset="UTF-16"/>
<HTML>
<HEAD>
</HEAD>
<script>
var formula_1 = "3-2";
var result="";
var queue=[];
var stack=[];
function Shunting_Yard_Algorithm()
{
for(var i=0;i<formula_1.length;i++)
{
//result += formula_1[i];
switch(formula_1[i])
{
case 0:
case 1:
case 2:
case 3:
case 4:
case 5:
case 6:
case 7:
case 8:
case 9:
queue += formula_1[i];
break;
case +:
case -:
//case *:
//case /: //乘除晚些再處理(handle later)
stack.push(formula_1[i]);
break;
default:
alert("out of control(預料之外)");
}
}
// alert(result); //測試字串是否正常
//alert(stack); //看堆疊內容
result += queue;
while(stack.length>0)
{
result += stack.pop();
}
alert(result); //看看字串結果如何,see string state
}
Shunting_Yard_Algorithm(); //要呼叫(call)一次才會運作
</script>
<BODY>
</BODY>
</HTML>
---(編程遇到的麻煩)
36-243624-會看不出是362-4還是3-624因此似乎是在讀入時就要處理
啊,可以之後再跟原字串比對突然想到KMP跟其它兩種字串比對演演算法等一下...數值裁切有三種可能一個是碰到字串結束另一個是碰到運算符號最後一個是碰到右括弧(碰到左括弧的處理法會牽扯到設計理念的問題,在此先不想那麼麻煩的情況)我先看下數值轉字串是否麻煩嗯,不麻煩,那感覺存數字較好
有幾個變數,就用幾個數值陣列(以後處理大數值運算是否會有困擾再另外想)不過還有個麻煩佇列...有可能會存運算符號,例如3*5-2*435*24*-那...數值存完之後,再多存一格空白當分野的話(以空間換取時間)也可以說是,運算符號壓入棧(stack)前,多存個空格(左括弧依然是個有些麻煩的存在,但先處理較簡單的情形暫時不予理會)也就是存成3 5 *2 4 *-表面上看起來好像沒差但若寫成 12*34-56*78可能就看得出差別了1234*5678-*沒空格看不出是誰乘誰誰減誰這方法雖然不是很聰明,不過...似乎可行再不行的話我就要先去睡覺想解答了!!(久違的直播編程睡覺)(結果後來沒睡,今天精神不錯但19:00也差不多該睡了 程式詳細說明與細節晚些再補)先思考下怎樣的後序運算式、中序運算式是合理的?首先後序運算式必然以數字開頭,運算符號做結尾再來,每次運算只需要兩個數字1+2*(3+4)-5/33 4 + 2 * 1 + 5 3 / -由左至右算過去(因此日後加入括弧與乘法要改的是產生後綴式的部分)呀,不太對勁5 3 /那邊還是要多個數字也就是說,除去一開頭兩個數字外,連遇到兩次數字就要再用個變數存那應該頂多只會用到三個變數吧?其實我也不太能肯定!!雖然隱約覺得是對的(若錯的話那式子會很複雜)修改後的程式長這樣(網址晚些再補)y541258/HTML5我用Mozilla(名字由來似乎是Mo://a) Firefox 58.0.2版顯示合乎預期<!DOCTYPE html>
<meta charset="UTF-16"/>
<HTML>
<HEAD>
</HEAD>
<script>
var formula_1 = "36-24-6";
var result="";
var result_number = 0;
var queue=[];
var stack=[];
var current_number=0;
var temp_number_middle=0;
var temp_number_right=0;
var set_flag=false;
//var more_digit_flag=false;
function Shunting_Yard_Algorithm()
{
for(var i=0;i<formula_1.length;i++)
{
//result += formula_1[i];
switch(formula_1[i])
{
case 0:
case 1:
case 2:
case 3:
case 4:
case 5:
case 6:
case 7:
case 8:
case 9:
queue += formula_1[i];
break;
case +:
case -:
//case *:
//case /: //乘除晚些再處理(handle later)
queue += " ";
stack.push(formula_1[i]);
break;
default:
alert("out of control(預料之外)");
}
}
if(Number.isInteger(parseInt(formula_1[formula_1.length-1])))
{
queue += " ";
}
//↑處理字串結束時數值也正好結束的特例,
//也許有字串結束字元等更聰明的方法,但我現階段想偷懶
result += queue;
while(stack.length>0)
{
result += stack.pop();
}
//alert(result); //看看字串結果如何,see string state
for(var i=0;i<result.length;i++)
{
switch(result[i])
{
case 0:
case 1:
case 2:
case 3:
case 4:
case 5:
case 6:
case 7:
case 8:
case 9:
if(!set_flag)
{
if(current_number==0)
{
current_number= result[i];
set_flag=true;
i++
while(Number.isInteger(parseInt(result[i])))
{
current_number = current_number*10 + parseInt(result[i]);
i++;
}
console.log("i=" + i);
//↑在Firefox,Chrome,Opera,Vivaldi中,
//按F12切到Console或主控台可以看偵錯資訊
}
}
else
{
//暫時不考慮輸入的式子是錯誤的狀況
if(temp_number_middle == 0)
{
temp_number_middle = parseInt(result[i]);
}
else
{
temp_number_middle *= 10;
temp_number_middle += parseInt(result[i]);
//也可以寫成temp_number_middle = temp_number_middle*10 + parseInt(result[i]);
}
console.log("temp_number_middle=" + temp_number_middle);
}
break;
case +:
if(temp_number_right==0)
{
result_number = current_number + temp_number_middle;
current_number = result_number;
}
else
{
temp_number_middle = temp_number_middle + temp_number_right;
temp_number_right=0;
}
break;
case -:
if(temp_number_right==0)
{
result_number = current_number - temp_number_middle;
current_number = result_number;
}
else
{
temp_number_middle = temp_number_middle - temp_number_right;
temp_number_right=0;
}
break;
break;
//case *:
//case /: //乘除晚些再處理(handle later)
case :
if(Number.isInteger(parseInt(result[i+1])))
{
temp_number_right = result[i+1];
i++;
while(Number.isInteger(parseInt(result[i+1])))
{
temp_number_right = temp_number_right*10 + result[i+1];
i++;
}
}
break;
default:
alert("out of control(預料之外)");
}
}
alert(result_number);
}
Shunting_Yard_Algorithm(); //要呼叫(call)一次才會運作
</script>
<BODY>
</BODY>
</HTML>
但這樣的程式會有個問題
例如把算式改成36- 24 – 6理論上要出來的結果是36 24 - 6 - ,然後計算的答案是6但實際上是這樣↓運算的36 24 6 - -也就是運算符號優先權相同時要把堆疊彈出個符號到佇列中這也是為何之前說佇列裡面會存運算符號!!3/11 19:27突然想到調度場演演算法 不把計算結果列出來的原因這單純只是個人的猜想或說感覺因為若要把值算出來在做的事情就挺像 編譯器 了個人是有想要用全域變數 與 對象 模擬 樹 來達成全域變數是為了走訪到 運運算元 節點 時再呼叫 對象 擁有的 方法 計算值並返回不過目前還處在僅是想想的狀態還沒下定決心去做可能等放假吧!!能算出這個跟編譯器的差別就在於還沒有變數的概念也就是我腦中所想的程序就算寫出來也還不算Parser,沒拆解成BNF的形式不過我想這應該算是個不錯的練習雖然在真正應對這挑戰前我先是有些怯場與慵懶了只是這樣的話我突然有個疑問那就是調度場演演算法與編譯器或parser相比不太清楚是專用來做什麼的可以把運算式從中序轉成後序沒錯可是...把RPN(逆波蘭表達式,後綴表達式)轉成樹再後序走訪一次感覺也很費工夫啊都做到這份上了感覺一併把Parser解決了學習會更完整(轉成樹再後序走訪這餿主意是個人思考一陣子想嘗試的可能有誤)嗯,我再仔細思考跟整頓心態假日時再試著挑戰其實我昨天休假時有挑戰過寫到一半發現無法窮舉才想起來以前學的Parser、編譯器會用到的BNF格式跟樹的後序走訪RPN要轉成 樹 還需要一個步驟我需要想清楚初步估計是從行末往前最尾巴的元素是根(root)節點再往前若是運運算元就送到左子樹然後...不過情況複雜時是否有個較易懂的規律我覺得我自己還沒想清楚若順利的話還會更新的不順利的話,哪天放棄了就找現成的答案貼網址或複製到Github來作結吧************
許久沒更新文章(上次是2018/03/11)
標題因為字數允許長度有修改過
因此簡化標題
雖然現在離寫出太閣立志傳那樣的小遊戲還有些距離
但只剩微小的距離
以前的問題其實沒解決
只是在Javascript中
字串的處理較C語言簡單許多
可透過正規表達式少去許多困擾
更新的程式碼在
(雖然目前運運算元優先順序是寫死在if裡面,這部份是還可以改良啦)
y541258/HTML5<!DOCTYPE html>
<meta charset="utf-8">
<html>
<body>
<textarea id="input_data"></textarea>
<button id="run">執行</button>
<div id="div_test"></div>
<script>
run.addEventListener("click",compute);
var expression_wait_parse=[];
var op_stack=[];
var postfix_result=[];
function compute(){
postfix_result=[];
document.getElementById("div_test").innerHTML = document.getElementById("input_data").value+"<br>";
expression_wait_parse = document.getElementById("input_data").value;
expression_wait_parse= expression_wait_parse.replace(/s/g,"");
expression_wait_parse = expression_wait_parse.split(/(-?d*.?d+)|([()])/);
for(var i=1;i<expression_wait_parse.length-1;i++)
{
if(!expression_wait_parse[i])
{
if(/-/.test(expression_wait_parse[i+1]))
{
expression_wait_parse[i]="-";
expression_wait_parse[i+1]=(expression_wait_parse[i+1]*-1).toString();
}
}
}
expression_wait_parse=expression_wait_parse.filter(function(e){return e});
alert(expression_wait_parse);
for(var i=0;i<expression_wait_parse.length;i++)
{
if(/d/.test(expression_wait_parse[i]))
{
postfix_result.push(expression_wait_parse[i]);
}
else if(/[+-*/]/.test(expression_wait_parse[i]))
{
console.log(expression_wait_parse[i]);
if(op_stack.length < 1)
{
op_stack.push(expression_wait_parse[i]);
}
else
{
for(var j=op_stack.length-1; j>=0;j--)
{
if(op_stack[j]=="(")
{
break;
}
if((op_stack[j]=="+" || op_stack[j]=="-") && (expression_wait_parse[i]=="+" ||expression_wait_parse[i]=="-"))
{
postfix_result.push(op_stack.pop());
}
if((op_stack[j]=="*" || op_stack[j]=="/") && (expression_wait_parse[i]=="*" ||expression_wait_parse[i]=="/"))
{
postfix_result.push(op_stack.pop());
}
if((op_stack[j]=="*" || op_stack[j]=="/") && (expression_wait_parse[i]=="+" ||expression_wait_parse[i]=="-"))
{
postfix_result.push(op_stack.pop());
}
}
op_stack.push(expression_wait_parse[i]);
}
console.log(op_stack);
}
else if(/(/.test(expression_wait_parse[i]))
{
op_stack.push(expression_wait_parse[i]);
}
else if(/)/.test(expression_wait_parse[i]))
{
var temp = op_stack.pop();
while(temp!="(")
{
postfix_result.push(temp);
temp = op_stack.pop();
alert(postfix_result);
}
}
}
for(var i=op_stack.length-1;i>=0;i--)
{
postfix_result.push(op_stack.pop());
}
document.getElementById("div_test").innerHTML += postfix_result+"<br>";
var compute_stack=[];
var num1,num2;
for(var i=0;i<postfix_result.length;i++)
{
if(/d/.test(postfix_result[i]))
{
compute_stack.push(postfix_result[i]);
}
else if(/[+-*/]/.test(postfix_result[i]))
{
num2 = compute_stack.pop();
num1 = compute_stack.pop();
compute_stack.push(eval(num1+postfix_result[i]+num2));
}
}
document.getElementById("div_test").innerHTML += "計算結果" + compute_stack.pop()+"<br>";
}
</script>
</body>
</html>
推薦閱讀：
TAG:思考 |