天天看點
傳回

用C語言寫一個電腦用C語言寫一個電腦

用C語言寫一個電腦

用C語言寫一個電腦，除了四則混合運算之外，還支援三角函數和絕對值等函數。

PS E:\Code\PL\calc> .\a.exe     
abs(3*5-4^2)
abs(3*5-4^2)=1.000000
25-7+6*(4-5)
25-7+6*(4-5)=12.000000

文章目錄

  • 用C語言寫一個電腦
    • 1. 加減法運算
    • 2. 加法和乘法
    • 3. 四則混合運算
    • 4. 浮點型電腦程式
    • 5. 加入三角函數

在電腦中，至少包含兩類變量，即數字和運算符。例如，如果希望實作 a + b × ( c − d ) a+b\times (c-d) a+b×(c−d)這樣一個簡單的功能，要求編譯器可以識别出 + , × , − , ( , ) +,\times,-,(,) +,×,−,(,)這五個符号，并理清彼此的計算順序，最後生成一棵文法樹，然後實作輸出。

1. 加減法運算

萬事開頭難，是以我們選擇一個簡單到無腦的開頭。首先，我們考慮實作 a + b a+b a+b這樣簡單的兩數運算，即如下所示，十分簡單且無腦。

void douCalc(){
    while (1){
        double i, j, s;
        char k;
        scanf("%lf%c%lf", &i, &k, &j);
        switch (k){
        case '+':
            s = i+j;
            break;
        case '-':
            s = i-j;
            break;
        case '*':
            s = i*j;
            break;
        case '/':
            s = i/j;
            break;
        default:
            break;
        }
        printf("%lf\n", s);
    }
}

然後，我們考慮，如何實作一個連加器，旨在解決 a + b + c + . . . a+b+c+... a+b+c+...的計算問題。這裡雖然不涉及到運算次序，但仍舊需要處理多個不确定個數的變量，是以我們不再可以直接用類似

scanf("%lf%c%lf", &i, &k, &j);

的方案來實作資料的輸入，而必須建立一個連結清單來存儲變量。

C語言輸入輸出

在C語言中，可以通過至少三種方式來讀取鍵盤輸入的值：

  • scanf()

     ：和 printf() 類似，scanf() 可以輸入多種類型的資料。

  • getchar()

     、

    getche()

     、

    getch()

     ：這三個函數都用于輸入單個字元。

  • gets()

     ：擷取一行資料，并作為字元串處理。

其中，

scanf

是格式化掃描的意思，可以通過格式控制符對輸入字元進行格式化，并指派給相關變量。

格式控制符 說明
%c 讀取單一字元
%s 讀取一個字元串（以空白符為結束）
%f、%lf 讀取十進制形式小數，指派給float、double 類型
%e、%le 讀取指數形式小數，指派給 float、double 類型
%g、%lg

讀取十進制或指數形式的小數，

并分别指派給 float、double 類型
  • 整數格式化
    short int long
    十進制 %hd %d %ld
    八進制 %ho %o %lo
    十六進制 %hx %x %lx
    無符号 %hu %u %lu

getchar()

等價于

scanf("%c", c)

，相對來說更加簡單。

getche

和

getch

是Windows獨有的函數，在頭檔案

conio.h

中故不贅述。

gets

和

scanf(%s,s)

的差別在于，後者在使用的過程中會把空格當作終止符，而前者不會。

是以，我們在實作連加的過程中，會使用

gets

作為互動方法。

由于我們實作的是一個連加器，是以輸入字元中隻包含數字和加号，那麼接下來，我們需要周遊輸入字元，通過加号來将數字分開。我們可以很友善地寫下一個簡單而醜陋的小程式。

void adds(){
    char str[100];
    char numStr[20];
    int num[20];       
    int val;
    int i,j,k;
    while (1){
        gets(str);
        i = 0;j = 0;k = 0;
        while (str[i]!='\0'){
            if (str[i]=='+'){
                num[k] = atoi(numStr);
                k++;
                j = 0;
            }else{
                numStr[j] = str[i];
                j++;
            }
            i++;
        }
        num[k]=atoi(numStr);
        val = 0;
        for (int i = 0; i < k+1; i++){
            val += num[i];
        }
        printf("%d\n",val);
    }
}

int main(){
    adds();
    return 0;
}

由于加減法具有相同的運算優先級，在實作上不過是為後續的數字加上一個負号而已，故可十分友善地在原有程式上修改。

此外，

adds

代碼乍看上去沒什麼問題，但

str

的值在更新之前，并不會自動清零，由此帶來的bug需要建立一個字元串清零的函數。修改之後的代碼如下

#include <stdio.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

void strClear(char *str,int n){
    for (int i = 0; i < n; i++){
        str[i]=NULL;
    }
}

void adds(){
    char str[100];
    char numStr[20];
    int num[20];       
    int val;
    int i,j,k;
    while (1){
        gets(str);
        i = 0;j = 0;k = 0;
        while (str[i]!='\0'){
            if (str[i]=='+'){
                num[k] = atoi(numStr);
                strClear(numStr,20);
                k++;
                j = 0;
            }else if (str[i]=='-'){
                num[k] = atoi(numStr);
                strClear(numStr,20);
                k++;
                numStr[0] = str[i];
                j = 1;
            }else{
                numStr[j] = str[i];
                j++;
            }
            i++;
        }
        num[k]=atoi(numStr);
        strClear(numStr,20);
        val = 0;
        for (int i = 0; i < k+1; i++){
            val += num[i];
        }
        printf("%d\n",val);
    }
}

int main(){
    adds();
    return 0;
}

精簡一下

#include <stdio.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

void strClear(char *str,int n){
    for (int i = 0; i < n; i++){
        str[i]='\0';
    }
}
void adds1(){
    char str[100];
    char numStr[20];
    int i,j,val;
    while (1){
        gets(str);
        i = 0;j = 0;val = 0;
        while (str[i]!='\0'){
            if ((str[i]=='+')||(str[i]=='-')){
                val += atoi(numStr);
                strClear(numStr,20);
                j = 0;
                if (str[i]=='-')
                    numStr[j++]=str[i];
            }else
                numStr[j++] = str[i];
            i++;
        }
        val += atoi(numStr);
        strClear(numStr,20);
        printf("%d\n",val);
    }
}



int main(){
    adds1();
    return 0;
}

2. 加法和乘法

若希望加入乘法和除法，那麼修改代碼的過程就相對複雜了，因為乘除法在運算過程中，具有比加減法更高的優先級。那麼我們就無法通過一個簡單的數組來存儲變量，而必須建立一種樹形的結構。

例如，對于 a + b × c − d × e / f a+b\times c-d\times e/f a+b×c−d×e/f，可寫成如下形式

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-ruufs0c0-1608717185925)(img/calc1.png)]

用C語言寫一個電腦用C語言寫一個電腦

我們可以看到，這是一個二叉樹，每個葉節點都是數字，而兩個葉節點的父節點則為運算符。我們通過這個運算符來計算其子節點後，删除它的兩個子節點，同時運算符所對應的節點退化為葉節點，同時其類型也變為數字。

對于上圖而言，先計算 e / f e/f e/f，然後計算 b × c b\times c b×c和 d × e / f d\times e/f d×e/f，再計算 b × c − d × e / f b\times c-d\times e/f b×c−d×e/f，最後計算最上面的加法。

對于樹來說，我們的周遊往往從根節點開始，是以其計算規則如下：

  1. 如果目前節點的子節點為葉節點，則計算目前節點，并删除該節點的葉節點，然後考慮其父節點。
  2. 如果目前節點的某個子節點不是葉節點，則處理該子節點，直到該子節點成為葉節點為止。
  3. 如果目前節點為根節點，且為葉節點，則輸出計算結果。

對于節點來說，除了父子節點外，則至少有兩個屬性：

  1. isLeaf：用于葉節點判定。在這裡，葉節點不僅有結構上的意義，更有着明确的語義：它隻能是數字。
  2. value：對于葉節點而言，這個值為數字，否則的話，這個值為運算符号及其所對應的計算規則。 
# define MAXLEN 100
typedef struct NODE{
    struct NODE *father;
    struct NODE *Left;
    struct NODE *Right;
    char value[MAXLEN];
    int isLeaf;
}Node;

生成計算樹

由于我們規定了兩個運算層級，是以再周遊字元串以生成計算樹的過程中，需要兩次循環，即首先生成加減法的計算樹，然後再生成乘除法的計算樹。

生成計算樹的過程可以簡化為字元串不斷拆分的過程，為了簡化思維，我們隻考慮兩個符号

+

和

*

，這兩個符号分别代表兩種計算層級。

由此可得到如下代碼。對于

# define TRUE 1
# define FALSE 0
void newNode(Node *root, Node *father){
    root -> father = father;
    root ->Left = NULL;
    root -> Right = NULL;
    root -> isLeaf = FALSE;
}

//root 為根節點，str為字元串
void initCalcTree(Node *root, char flag){
    for (int i = 0; i < MAXLEN; i++){
        if (root->value[i]==flag){
            Node *Left = (Node *)malloc(sizeof(Node));
            Node *Right = (Node *)malloc(sizeof(Node));
            newNode(Left,root);
            newNode(Right,root);

            for (int j = 0; j < i; j++)
                Left -> value[j] = root->value[j];
            Left->value[i] = '\0';
            i++;
            for (int j = i; j < MAXLEN; j++)
                Right -> value[j-i] = root->value[j];

            root->Left = Left;
            root->Right = Right;

            strClear(root->value,MAXLEN);
            root->value[0] = flag;
            root->value[1] = '\n';
            
            initCalcTree(Left,'*');
            if (flag=='+')
                initCalcTree(Right,'+');
            else
                initCalcTree(Right,'*');
            break;
        }else{
            if (root->value[i]=='\0'){
                if(flag =='+')
                    initCalcTree(root,'*');
                else
                    root -> isLeaf = TRUE;
                break;
            }
            else
                continue;

        }
    }
}

測試一下

void printNode(Node *root,int start){
    printf("the %dth node is %s\n", start, root->value);
    if (root->isLeaf==FALSE){
        printNode(root->Left, start + 1);
        printNode(root->Right, start + 1);
    }
}

int main(){
    Node *root = (Node *)malloc(sizeof(Node));
    char *str = "1+21*3+3*4*5+6";
    strcpy(root->value,str);
    initCalcTree(root,'+');
    printNode(root,0);
    return 0;
}

得到結果為

the 0th node is +

the 1th node is 1
the 1th node is +

the 2th node is *

the 3th node is 21
the 3th node is 3
the 2th node is +

the 3th node is *

the 4th node is 3
the 4th node is *

the 5th node is 4
the 5th node is 5
the 3th node is 6

然後，我們再對計算樹進行計算。當被計算的量為葉節點時，則傳回該節點的值；如果該節點的兩個節點都是葉節點，則傳回該節點處的運算符對這兩個子節點的計算值；如果該節點的兩個節點都不是葉節點，那麼對這兩個子節點進行計算。

int calcNode(Node *root){
    if(root->isLeaf == TRUE)
        return atoi(root->value);
    else if (root->Left->isLeaf * root->Right->isLeaf == TRUE){
        if(root->value[0] == '+')
          return atoi(root->Left->value)+atoi(root->Right->value);
        else
          atoi(root->Left->value)*atoi(root->Right->value);
    }else{
        if (root->value[0] == '+')
            return calcNode(root->Left)+calcNode(root->Right);
        else
            return calcNode(root->Left)*calcNode(root->Right);
    }
}

int main(){
    Node *root = (Node *)malloc(sizeof(Node));
    char str[MAXLEN];
    while (1){
        gets(str);
        strcpy(root->value,str);
        initCalcTree(root,'+');
        printf("%s=%d\n",str,calcNode(root));
    }
    return 0;    
}

結果為

PS E:\Code\PL\calc> .\a.exe
1+2+3*4+15*2
1+2+3*4+15*2=45
2*5+3*6*12
2*5+3*6*12=226

3. 四則混合運算

如果考慮加減乘除，那麼意味着一個運算級别下有多種運算符，是以我們需要通過一個函數來傳回運算符的運算次序。

int getOrder(char ch){
    int result;
    switch (ch){
    case '+':
    case '-':
        return 0;
    case '*':
    case '/':
        return 1;
    default:
        return 2;
    }
}

然後，基于此，修改計算樹的生成與計算代碼。

int douCalc(char c,int a, int b){
    switch (c){
        case '+':
            return a+b;
        case '-':
            return a-b;
        case '*':
            return a*b;
        case '/':
            return a/b;
    }
}

void newNode(Node *root, Node *father){
    root -> father = father;
    root ->Left = NULL;
    root -> Right = NULL;
    root -> isLeaf = TRUE;
    father -> isLeaf = FALSE;
}


//root 為根節點，str為字元串，N為字元串長度
void initCalcTree(Node *root, int order){
    for (int i = 0; i < MAXLEN; i++){
        if (getOrder(root->value[i])==order){
            Node *Left = (Node *)malloc(sizeof(Node));
            Node *Right = (Node *)malloc(sizeof(Node));
            newNode(Left,root);
            newNode(Right,root);

            for (int j = 0; j < i; j++)
                Left -> value[j] = root->value[j];
            Left->value[i] = '\0';
            i++;
            for (int j = i; j < MAXLEN; j++)
                Right -> value[j-i] = root->value[j];

            root->Left = Left;
            root->Right = Right;

            root->value[0] = root->value[i-1];
            root->value[1] = '\0';
            
            initCalcTree(Right,order);
            if (order<1)
                initCalcTree(Left,order+1);
            break;
        }
        else if((i==0)&&(order<2))
            initCalcTree(root,order+1);
    }
}
int calcNode(Node *root){
    if(root->isLeaf == TRUE)
        return atoi(root->value);
    else if (root->Left->isLeaf * root->Right->isLeaf == TRUE)
        return douCalc(root->value[0],
            atoi(root->Left->value),atoi(root->Right->value));
    else
        return douCalc(root->value[0],
            calcNode(root->Left),calcNode(root->Right));
}
int main(){
    Node *root = (Node *)malloc(sizeof(Node));
    char str[MAXLEN];
    while (1){
        gets(str);
        strcpy(root->value,str);
        initCalcTree(root,0);
        printf("%s=%d\n",str,calcNode(root));
    }
    return 0;    
}

至此，我們得到了一個電腦的“骨架”，為運算符設定相應的運算次序，相當于提供一種生成方法，這種方法可以直接擴充到更多的運算符上。

同時，上述代碼中也出現了兩個問題：

  1. 我們預設計算的是整型資料，是以無法處理浮點型運算
  2. 減法和除法雖然在名義上與加法、乘法處于相同的運算次序中，但我們的生成樹中預設的是從右向左計算。對于 a + b − c + d a+b-c+d a+b−c+d這樣的表達式，會計算成 a + b − ( c + d ) a+b-(c+d) a+b−(c+d)的形式，這是錯誤的。

針對這種運算結構的一個優勢和兩個問題，我們繼續改進這個電腦程式。

4. 浮點型電腦程式

首先，我們将所有函數與變量均改為

double

類型；然後我們更改輸入字元串的周遊方式，從後向前進行周遊。

我們再加入乘方運算符

^

，給它一個更高的運算層級

int getOrder(char ch){
    int result;
    switch (ch){
    case '+':
    case '-':
        return 0;
    case '*':
    case '/':
        return 1;
    case '^':
        return 2;
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':
        return 3;
    default:
        return 4;
    }
}

double douCalc(char c,double a, double b){
    switch (c){
        case '+': return a+b;
        case '-': return a-b;
        case '*': return a*b;
        case '/': return a/b;
        case '^': return pow(a,b);
    }
}

至此，我們寫出了一個可以計算

+-x÷^

的程式。但我們還不能處理表達式中可能出現的括号。

括号在表達式中成對出現，故不同于正常運算符，需要在表達式的兩端進行周遊；另外，括号不具備運算功能，隻有規定運算次序的作用，對于括号運算符隻有一個子節點。是以，隻需更改

initCalcTree

的代碼。

由于我們将算法改為從右向左周遊，是以如果最後一個字元不是

)

，則不必考慮括号的影響。當最後一個字元為

)

時，如果第0個字元為

(

，則将括号裡面的内容提取出來，針對此時的節點重新進行周遊即可。如果自左向右周遊的過程出現第一個

(

的位置是

posLeft

，則後面關于運算符的周遊從

posLeft

開始。

//root 為根節點，str為字元串，N為字元串長度
void initCalcTree(Node *root, int order){
    int lenStr = strlen(root->value);
    int posLeft = lenStr;
    //如果末尾為')'，則查找其對應的左括号的位置
    if(root->value[lenStr-1]==')'){
        for (int i = 0; i < lenStr; i++)
            if(root->value[i]=='(')
                    posLeft = i;
        if (posLeft == 0){
            for (int i = 1; i < lenStr-1; i++)
                root->value[i-1] = root->value[i];
            root->value[lenStr-2]='\0';
            initCalcTree(root,0);
        }
    }
    //如果左括号的位置不為0，則
    for (int i = posLeft; i >= 0; i--){
        if (getOrder(root->value[i])==order){
            Node *Left = (Node *)malloc(sizeof(Node));
            Node *Right = (Node *)malloc(sizeof(Node));
            newNode(Left,root);
            newNode(Right,root);

            for (int j = 0; j < i; j++)
                Left -> value[j] = root->value[j];
            Left->value[i] = '\0';
            i++;
            for (int j = i; j < MAXLEN; j++)
                Right -> value[j-i] = root->value[j];

            root->Left = Left;
            root->Right = Right;

            root->value[0] = root->value[i-1];
            root->value[1] = '\0';  //字元串末尾标記
            
            initCalcTree(Left,order);
            if ((order<2)||(posLeft!=lenStr))
                initCalcTree(Right,order+1);
            break;
        }
        else if((i==0)&&(order<2))
            initCalcTree(root,order+1);
    }
}

至此，我們就寫好了一個簡陋的可以進行四則混合運算的電腦程式

PS E:\Code\PL\calc> .\a.exe     
1+2*(3-4)+5
1+2*(3-4)+5=4.000000
2^(3+1)
2^(3+1)=16.000000

5. 加入三角函數

現在我們需要考慮加入三角函數，其難點在于函數的識别。

我們規定，單變量函數通過括号的方式導入實參，也就是說，隻要表達式中不出現括号，那麼就不必考慮括号的問題。換句話說，判定函數，必然在判定括号之後。

考慮到我們定義的

getOrder

函數中，除了我們所規定的符号和數字之外，其他符号和字母的預設傳回值為4。是以需要在判定括号之後，繼續進行函數的判斷。

故而需要更改括号判定的代碼

/*...*/
    if(root->value[lenStr-1]==')'){
        for (int i = 0; i < lenStr; i++)
            if(root->value[i]=='(')
                     posLeft = i;
        if (posLeft == 0){
            for (int i = 1; i < lenStr-1; i++)
                root->value[i-1] = root->value[i];
            root->value[lenStr-2]='\0';
            initCalcTree(root,0);
        }else{            
            int lenFunc=0;
            posLeft--;
            while ((getOrder(root->value[posLeft])==4)&&(posLeft>0)){
                posLeft--;
                lenFunc++;}
            //當posLeft變為0時，說明此節點為無法分割的函數
            if (posLeft==0){
                root->value[lenFunc+1]='\0';
                Node *Left = (Node *)malloc(sizeof(Node));
                root->Left = Left;
                newNode(Left,root);
                for (int i = lenFunc+2; i < lenStr-1; i++){
                    Left->value[i-lenFunc-2]=root->value[i];
                }
                Left->value[lenStr-lenFunc-2]='\0';
                initCalcTree(Left,0);   //對左子節點進行生成
                return 0;
            }
        }
    }
/*...*/

接下來，我們需要修改

calcNode

函數，即在計算運算符之前，添加一個函數處理程式。其中，

strcmp

為字元串比對函數，當兩個字元串相等時，傳回0。

double doFunc(char *str,double val){
    if (strcmp(str,"sin")==0)
        return sin(val);
    else if (strcmp(str,"cos")==0)
        return cos(val);
    else if (strcmp(str,"tan")==0)
        return tan(val);
    else if (strcmp(str,"arcsin")==0)
        return asin(val);
    else if (strcmp(str,"arccos")==0)
        return acos(val);
    else if (strcmp(str,"arctan")==0)
        return atan(val);
    else if (strcmp(str,"sqrt")==0)
        return sqrt(val);
    else if (strcmp(str,"abs")==0)
        return abs(val);    
}

double calcNode(Node *root){
    if(getOrder(root->value[0])==4)
        return doFunc(root->value,calcNode(root->Left));
    if(root->isLeaf == TRUE)
        return atof(root->value);
    else if (root->Left->isLeaf * root->Right->isLeaf == TRUE)
        return douCalc(root->value[0],
            atof(root->Left->value),atof(root->Right->value));
    else
        return douCalc(root->value[0],
            calcNode(root->Left),calcNode(root->Right));
}

至此，我們已經用C語言實作了一個簡陋而且有不少bug的電腦，比如并未設定除零報警之類的功能，但一般的操作是沒有問題的。

abs(3*5-4^2)
abs(3*5-4^2)=1.000000
25-7+6*(4-5)
25-7+6*(4-5)=12.000000
程式設計語言學習 c語言 電腦 編譯原理 文法生成樹 字元串
上一篇: 商業資料分析從入門到入職（5）Python基本文法和資料類型一、從計算機到Python二、Python的簡單使用三、Python基本數值資料類型四、字元串操作
下一篇: C語言實作一個簡單的電腦

繼續閱讀