[思路]LeetCode Problems- 537. Complex Number Multiplication

 這次要來解決的問題是複數相乘Complex Number Multiplication.
C語言不像在大學時期所碰的MATLAB一樣有方便的數學函數工具箱,可以幫學生做計算-----應該說要用C計算數學也是可以,但基本上兩種軟體的功用大不相同-----這次的問題在為自己將來有可能會碰到MATLAB轉C的需求作準備.
題目原文如下:

Given two strings representing two complex numbers.

You need to return a string representing their multiplication. Note i2 = -1 according to the definition.

Example 1:

Input: "1+1i", "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

Example 2:

Input: "1+-1i", "1+-1i"
Output: "0+-2i"
Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.

Note:

1. The input strings will not have extra blank.
2. The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. And the output should be also in this form.

題目的大意為給定兩個以a+bi表示的複數,並且還是字串的形態,
求兩個複數相乘的結果,同樣要以a+bi及字串的型態來表示

首先,兩個字串相乘的結果為:

無論abcd輸入的值是正還是負,相乘出來的結果永遠會是 實部=a*c-b*d     虛部=a*d+b*c

至此,我們可以想出程式運作的流程如下:

由於輸入的型態是字串不能直接做運算,故要把數字部分提出來,做完運算後再放回字串中,回傳給程式就完成了.

然而正當我要開始撰寫時,卻為leetcode網頁上規範的函數格式感到困惑不已,leetcode網站給的初始程式碼是這樣的:

char* complexNumberMultiply(char* a, char* b) {
 
}
此函式用到的不是一般所常見的char字元陣列,而是多了個間接運算子*的指標記號.
而這跟單純的char陣列有何不同呢?

根據 Stephen Prata所著的 C Primer Plus 6th Edition關於指標與陣列的差別:

"....What is the difference, then, between an array and a pointer form? The array form ( ar1[] ) causes an array of 29 elements (one for each character plus one for the terminating  '\0' ) to be allocated in the computer memory. Each element is initialized to the corresponding character of the string literal. Typically, what happens is that the quoted string is stored in a data segment that is part of the executable file; when the program is loaded into memory, so is that string. The quoted string is said to be in  static memory . But the memory for the array is  allocated only after the program begins running. At that time, the quoted string is copied into the array. ...."
使用 char ar1[] 這種語法所宣告出來的是實實在在的陣列(加上結束字元/0)每個字元元素被配置於陣列所需的電腦記憶體

"...... The pointer form ( *pt1 ) also causes 29 elements in static storage to be set aside for the string. In addition, once the program begins execution, it sets aside one more storage location for the pointer  variable   pt1  and stores the address of the string in the pointer variable. This variable initially points to the first character of the string, but the value can be changed. Therefore, you can use the increment operator. For instance,  ++pt1  would point to the second character ( o )........"
使用指標*pt1同樣也會產生字串,但還會多配置一貯存空間給指標變數pt1,所代表的是字串的位址,指向字串的第一個字元.

所以比較起來,一個是字元陣列,另一個是指向字串的指標,在實際使用上,兩種都可以使用陣列的語法,都可以加上指標,但只有指標型態的敘述才可以使用遞增運算子(例如pt1++)因此運算起來速度較快.
更多相似的語法可以再繼續參考此CEDN博客:深入 char * ,char ** ,char a[ ] ,char *a[] 内核
http://blog.csdn.net/daiyutage/article/details/8604720

回過頭來看此題目,若要分割字串的元素,我們可以用函式strtok:

[附註:有const關鍵字的原型,表示此字串不能被函數更改]

利用這個函式,我們就能把需要的數字分切出來:

char * pch;  
pch = strtok(a,"+"); //此時pch為實部

若要求出複數的虛部,則令原pch為NULL,把最後一段切出來:

pch = strtok (NULL, "+");//此時pch為虛部

分割出來後還要針對型態是字串的數字轉型為int才可以做運算,這時就會用到atoi():

char * pch;  
pch = strtok(a,"+");  
int a1 = atoi(pch);
pch = strtok (NULL, "+");
int b1 = atoi(pch);

atoi()可以忽略掉數字參雜複數符號i的情況,引述C Primer Plus 6th Edition關於atoi()的使用:
"...... The  atoi()  function still works if the string only begins with an integer. In that case, it converts characters until it encounters something that is not part of an integer. For example,  atoi("42regular")  returns the integer  42 . ......"

現在我們求出數字之後,就可以做複數相乘的計算:

int re=(a1*a2-b1*b2);
int im=(a1*b2+b1*a2);

算好之後還要再轉換回字串的型態.此時要注意不能用itoa()做轉換,編譯器不再支援此舊函式的使用,取而代之的是sprintf().它的運作方式類似於printf(),不同的是它會將資料輸出為字串而非輸出到螢幕上:

利用此函式我們可以把原先的int資料轉換成字串型態,如以下寫法:
char *W1[64];
char *W2[64];
sprintf(W1,"%d",re);    //把re的數值存進W1字串
sprintf(W2,"%d",im);   //把im的數值存進W2字串

最後,還需要把這兩個實部及虛部合起來以a+bi的表示式回傳,而字串的合併就需要使用到strcat():

使用此函式我們就可以將兩兩字串合併在一起:

strcat(strcat(W1,"+"),strcat(W2,"i"));

這樣最終就完成了整個程式

然而在傳送給leetcode時,卻又產生其他的問題
文章前面有提及到,leetcode網頁上把問題當成一個個函式來表述,故寫至結尾時要回傳數值給程式,
以我程式碼為例,我最後結尾會寫成

return W1;

回傳字串給程式.而看似最終submit接收不到我回傳的字串多少:

後來仔細檢查,才發覺這跟記憶體配置有密切的關係.
由於我宣告char陣列字元是屬於區域變數,
而當程式運作離開函式時,
原本存元素的記憶體位址就會被釋放出來,
回傳寫的位址將則變得一點意義都沒有
這跟C++ STL庫的string有所不同

若要讓函式中的陣列元素存在的話,就要把它改成是全域變數,即加上static:

    static char *W1[64];
    static char *W2[64];

就可以成功回傳字串了~
[附註2:另有一方法則是用動態記憶體配置malloc()]

這題的概念雖然看似簡單,但實際上還有許多眉眉角角要顧及到,
之後再來看其他題目,我們下周見~!