c++ 資料結構之中綴表達式

中綴表達式轉字尾表達式

所謂中綴，即常見的那種表達式，如 8+(3−1)×5 8 + ( 3 − 1 ) × 5

字尾表達式則是計算機内部實際的計算方式，如 831−5×+ 831 − 5 × +

轉換方法

對于”8+(3-1)*5”

先建立一個用來儲存符号的棧stack

從左開始周遊每個字元：

對于數字：

直接輸出

對于符号：

遇到左括号，進棧

遇到運算符号（+-*/），與棧頂的符号進行優先級比較，如果棧頂的優先級低，符号進棧（預設棧頂若是左括号，左括号優先級最低）。若棧頂符号優先級不低，先将棧頂符号彈出并輸出，之後再讓目前進棧。

遇到右括号，将棧頂符号彈出并輸出，直到比對左括号。（之後也把左括号彈掉，但不輸出到螢幕）

當字元串周遊完畢，把棧中所有符号彈出就結束。

計算字尾表達式

表達式：831-5* +

從左開始周遊每個字元：

對于數字：

直接入棧

對于符号：

從棧中彈出一個右操作數

再從棧中彈出一個左操作數

根據符号進行運算（左 符号 右 = 結果）

将結果壓入棧中

當周遊結束，棧中的唯一數字為計算結果。

(注：a+b，a為左操作數，b為右操作數)

實驗結果

代碼示例

#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;

//c++中純c文法


//---------------------------part1，自定義鍊式棧的實作
//用連結清單實作的後入先出的棧

//連結清單節點
typedef struct LINKNODE
{
    //注意是指針
    struct LINKNODE* next;
}LinkNode;
//棧，每個節點都是一個連結清單節點
typedef struct STACK
{
    LinkNode head;
    int size;
}Stack;
//自定義一個資料類型，且第一個元素放節點指針，也就是Person* 和 LinkNode*可以無縫互轉
typedef struct PERSON
{
    LinkNode *node;
    int age;
    char name[];
}Person;
//建立一個空棧
Stack* init()
{
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->size = ;
    stack->head.next = NULL;
}

//push，棧底在最後面棧頂和head連在一起
void push(Stack* stack,LinkNode* data)
{
    if(stack==NULL || data == NULL)
    {
        return;
    }
    data->next = stack->head.next;
    stack->head.next = data;
    //每次記得size+1啊
    stack->size ++;
}
//獲得棧頂
LinkNode* top(Stack* stack)
{
    if(stack==NULL || stack->size == )
    {
        return NULL;
    }
    return stack->head.next;
}
//出棧
void pop(Stack* stack)
{
    if(stack==NULL || stack->size ==)
    {
        return;
    }
    stack->head.next = stack->head.next->next;
    //這裡之前忘記--了
    stack->size --;
}
//棧是否為空
int isEmpty(Stack* stack)
{
    //注意了，是0傳回1
    if(stack->size == )
    {
        return ;
    }
    return ;
}
//測試棧
void test()
{
    Stack* stack = init();
    Person p1;
    Person p2;
    Person p3;
    Person p4;
    Person p5;
    printf("test\n");
    strcpy(p1.name,"aaa");
    strcpy(p2.name,"bbb");
    strcpy(p3.name,"ccc");
    strcpy(p4.name,"ddd");
    strcpy(p5.name,"eee");
    p1.age = ;
    p2.age = ;
    p3.age = ;
    p4.age = ;
    p5.age = ;
    push(stack,(LinkNode*)&p1);
    push(stack,(LinkNode*)&p2);
    push(stack,(LinkNode*)&p3);
    push(stack,(LinkNode*)&p4);
    push(stack,(LinkNode*)&p5);
    //後入先出
    for(int i = ;i<;i++)
    {
        printf("%d:%s\n",((Person*)top(stack))->age,((Person*)top(stack))->name);
        pop(stack);

    }
}

//---------------------------part2，中綴表達式轉字尾


//一個用來存放臨時的運算符，包括括号，+-*/
typedef struct MYDATA
{
    LinkNode* node;
    char c;
}MyData;

//判斷是左括号
int isLeft(char c)
{   
    if(c=='(')
        return ;
    return ;
}
//判斷右括号
int isRight(char c)
{   
    if(c==')')
        return ;
    return ;
}
//是否是數字
int isDigital(char c)
{
    if(c>='0' && c<='9')
    {
        return ;
    }
    return ;
}
//看看是否是運算符
int isOperator(char c)
{
    if(c=='+' ||c=='-' ||c=='*' ||c=='/')
    {
        return ;
    }
    return ;
}
//看看棧頂符号的優先級
int getPriority(char c)
{
    if(c=='+' ||c=='-')
    {
        return ;
    }
    if(c=='*' ||c=='/')
    {
        return ;
    }
}
//自己弄的列印
void print(char c)
{
    printf("%c",c);
}
//快速把一個字元變成棧頂
LinkNode* operatorNode(char c)
{
    MyData* data = (MyData*)malloc(sizeof(MyData));
    data->c = c;
    return (LinkNode*)data;
}
//提取棧頂元素中的字元
char extractTopChar(Stack* stack)
{
    return ((MyData*)top(stack))->c;
}

void test2()
{
    //char* str = "(8+(((3-1))*5))";//answer 831-5*+
    char* str = "1+(3*2+1*3+(5*1))";
    char* p = str;
    Stack* stack = init();
    printf("中綴表達式%s轉成字尾表達式是：",str);
    while(*p!='\0')
    {
        if(isDigital(*p))
        {
            //數字直接列印
           print(*p); 
        }
        if(isLeft(*p))
        {
            //遇到左括号直接入棧
            push(stack,operatorNode(*p));
        }
        if(isRight(*p))
        {
    //printf("test\n");
            //如果是右括号，直接彈出所有棧頂元素，直到遇到左括号
            while(extractTopChar(stack)!='(')
            {
                print(extractTopChar(stack));
                pop(stack);
            }
            //把剩下的左括号也彈掉
            pop(stack);
        }
        if(isOperator(*p))
        {
            //原本的棧是空的或者是左括号直接入棧
            if(isEmpty(stack) || isLeft(extractTopChar(stack)))
            {
                push(stack,operatorNode(*p));
            }
            //還要看看棧頂是不是加減符号，不然沒什麼好比的
            else if(isOperator(extractTopChar(stack)))
            {
                //若棧頂的優先級較低，新來的符号入棧
                if(getPriority(*p)>getPriority(extractTopChar(stack)))
                {
                    push(stack,operatorNode(*p));
                }else
                {
                    //否則要先出棧輸出再入棧
                    print(extractTopChar(stack));
                    pop(stack);
                    //入棧
                    push(stack,operatorNode(*p));
                }
            }
        }
        p++;
    }
    //把棧剩餘的内容都列印出來
    while(!isEmpty(stack))
    {
        print(extractTopChar(stack));
        pop(stack);
    }
    printf("\n");
}


//---------------------------part3，求解字尾表達式的值
//簡要原理，數字就壓棧，遇到運算符，就出棧頂當右值，再出一次棧頂當左值
//計算後再放回去，一直到把表達式字元串周遊完，棧中剩餘的元素就是最終的結果
int calc(char oper,int right,int left)
{   
    //int right = rightVal - '0';
    //int left = leftVal - '0';
    switch(oper)
    {
        case '+':return left+right;
        case '-':return left-right;
        case '*':return left*right; 
        case '/':return right==?-:(left/right); 
    }
}

//棧的資料節點稍微要改下，不是存char了，是int
typedef struct DATA
{
    LinkNode* node;
    int val;
}Data;

LinkNode* dataNode(int val)
{
    Data* data = (Data*)malloc(sizeof(Data));
    data->val = val;
    return (LinkNode*)data;
}

int extractTopInt(Stack* stack)
{
    return ((Data*)(top(stack)))->val;
}

void test3()
{
    //char* str = "831-5*+";
    char* str = "132*13*51*+++";
    //主要是拷貝一份，避免在原有資料上改
    char* p = str;
    //棧的主力軍變成int，part2是運算符
    Stack* stack = init();
    while(*p!='\0')
    {
        if(isDigital(*p))
        {
            int val = *p - '0';
            push(stack,dataNode(val)); 
        }
        if(isOperator(*p))
        {
            int rightVal = extractTopInt(stack);
            pop(stack);
            int leftVal = extractTopInt(stack);
            pop(stack);
            push(stack,dataNode(calc(*p,rightVal,leftVal)));
        }
        p++;
    }
    if(!isEmpty(stack))
    {
        printf("字尾表達式%s的計算結果是：%d\n",str,extractTopInt(stack));
    }
}

int main()
{
    //test();//測試棧
    test2();//中綴變字尾
    test3();
    return ;
}