添加使用堆垛狀排列的兩個數字

因此，舉例來說，如果我要加20 + 15，我需要有兩個數組：添加使用堆垛狀排列的兩個數字

a = {2, 0} 
b = {1, 5}

我應該得到以下數組作爲一個結果：

outcome = {3, 5} // or {5, 3} and read it in reverse order

最難的部分是我只能使用這些數組的第一個元素，以便它們像堆棧一樣工作。

在我的例子中它相對容易，但如果會有像{1, 0, 0, 0} + {5}這樣的數字呢？或{9, 9} + {9, 9}？

我真的不能找到一個具體的方法來做到這一點，更不用說我找不到任何解決{1, 0, 0, 0} + {5}。 C標籤在這裏是因爲我實際上需要用C語言編寫這個東西，但任何關於解決方案的想法都會受到歡迎（我的意思是描述，不一定是C程序）。

來源

2013-04-13 user2252786

你可以從數組的* end *而不是從頭開始彈出嗎？或者反轉數字？加法是從最少到最重要的數字完成的。 –

我不能做任何這些。 – user2252786

但是，如果這種方式沒有簡單的解決方案，我認爲如果有必要的話，我可以在最後反轉數字。 – user2252786

反轉數字，以便最低有效位數是第一位，最重要位數是最後一位。加法算法從最小到最顯着。

a = {0, 0, 0, 1} 
b = {5}

添加這些數字現在應該很簡單。從每個數字中彈出一個數字，添加它們，並將結果推送到結果堆棧。

a = {9, 9} 
b = {9, 9}

要處理99 + 99，您需要跟蹤進位。這將是一個額外的變量，你存儲不會進入任何堆棧。流行9和9，添加它們並獲得18.將8推入結果堆棧並存儲進位數字。

a = {9} 
b = {9} 
outcome = {8} 
carry = 1

現在流行的接下來的兩個數字，9,9，並加入他們得到18添加進位拿到19推9到成果堆棧，並再次跟蹤矣。

a = {} 
b = {} 
outcome = {9, 8} 
carry = 1

現在輸入堆棧上沒有數字了，所以最後將最後一個進位數字推到結果堆棧上。

outcome = {1, 9, 8}

來源

2013-04-13 15:46:33

嘗試此（未測試的）（更新處理攜帶）：

Stack Add(Stack a, Stack b, bool carry) { 
    if (a.Empty && b.Empty) return (carry ? a.Push(1) : a); 
    int c = (a.Empty ? 0 : a.Pop) 
     + (b.Empty ? 0 : b.Pop) 
     + (carry ? 1 : 0); 
    if (c>=10) 
    return Add(a,b,true).Push(c-10) 
    else 
    return Add(a,b,false).Push(c); 
}

當然，它是隱式使用函數調用棧以及一個和b。

來源

2013-04-13 15:43:32

@JonathanLeffler：現在呢？ –

呃...你讓我想......我會刪除我的評論，因爲它不再適用。 –

我覺得你最希望的是這樣一個算法：

pop digits from stack a and compute number n1 
pop digits from stack b and compute number n2 
add n1 and n2 giving n3 
push digits from n3 onto stack outcome

如果做不到這一點，你必須知道有多少位有每個堆棧中，a和b，這樣就可以將它們對齊正常。

的替代，但不太直觀，表示可以幫忙，太：

a = { 0, 2 } 
b = { 5, 1 } 

c = { 0, 0, 0, 1 } 
d = { 5 }

最低顯著位首先存儲。現在您可以根據需要從堆棧的前面開始添加和運載。

來源

2013-04-13 15:49:47

添加使用堆垛狀排列的兩個數字

回答

相關問題