使用棧實作表達式求值

#include <iostream>

#include <string>

#include <cmath>

using namespace std;

#define MAX_SIZE 7

#define MAX  1000

char rule[][7]={

                {'>', '>', '<', '<', '<', '>', '>'},

                {'>', '>', '<', '<', '<', '>', '>'},

                {'>', '>', '>', '>', '<', '>', '>'},

                {'>', '>', '>', '>', '<', '>', '>'},

                {'<', '<', '<', '<', '<', '=', '0'},

                {'>', '>', '>', '>', '0', '>', '>'},

                {'<', '<', '<', '<', '<', '0', '='}

};

char c_data[] = {'+','-','*','/','(',')','#'};

typedef struct node_pn{

    double value;

    struct node_pn* pNext;

}NODEPN;

typedef struct pn{

    int pnCount ;

    NODEPN* pnTop;

}STACKPN;

typedef struct node_pd{

    char value;

    struct node_pd* pNext;

}NODEPD;

typedef struct pd{

    int pdCount;

    NODEPD* pdTop;

}STACKPD;

void InitStackPD(STACKPD* &ptr_pd)

{

    ptr_pd = new STACKPD;

    ptr_pd->pdTop = NULL;

    ptr_pd->pdCount = 0;

}

void push_pd(STACKPD* &stackpd,NODEPD* ptr_pd)

{

    if(ptr_pd == NULL)  return ;

    if(stackpd->pdTop != NULL){

        ptr_pd->pNext = stackpd->pdTop;

    }

    stackpd->pdTop = ptr_pd;

    stackpd->pdCount++;

}

void top_pd(STACKPD* stackpd,NODEPD* &ptr_pd)

{

    if(stackpd== NULL || stackpd->pdTop == NULL) return ;

    ptr_pd = stackpd->pdTop;

}

void pop_pd(STACKPD* &stackpd)

{

    if(stackpd == NULL || stackpd->pdTop == NULL)  return ;

    NODEPD *ptr_pd = stackpd->pdTop;

    stackpd->pdTop = ptr_pd->pNext;

    stackpd->pdCount--;

    delete ptr_pd;

    ptr_pd = NULL;

}

void InitStackPN(STACKPN* &ptr_pn)

{

    ptr_pn = new STACKPN;

    ptr_pn->pnTop = NULL;

    ptr_pn->pnCount = 0;

}

void push_pn(STACKPN* &stackpn,NODEPN* ptr_pn)

{

    if(ptr_pn == NULL)  return ;

    if(stackpn->pnTop != NULL){

        ptr_pn->pNext = stackpn->pnTop;

    }

    stackpn->pnTop = ptr_pn;

    stackpn->pnCount++;

}

void top_pn(STACKPN* stackpn,NODEPN* &ptr_pn)

{

    if(stackpn== NULL || stackpn->pnTop == NULL) return ;

    ptr_pn = stackpn->pnTop;

}

void pop_pn(STACKPN* &stackpn)

{

    if(stackpn == NULL || stackpn->pnTop == NULL)  return ;

    NODEPN *ptr_pn = stackpn->pnTop;

    stackpn->pnTop = ptr_pn->pNext;

    stackpn->pnCount--;

    delete ptr_pn;

    ptr_pn = NULL;

}

int Find_Location(char c,char a[])

{

    for(int i=0;i<MAX_SIZE;i++){

        if(c == a[i]){

            return i;

        }

    }

    return -1;

}

char GetRel(char c_a,char c_b,char a[], char rule[][MAX_SIZE])

{

    if( Find_Location(c_a,a) == -1 || Find_Location(c_b,a) == -1)  return ' ';

    return rule[Find_Location(c_a,a)][Find_Location(c_b,a)];

}

void Deal(double a,char c,double b,double &Result)

{

    switch (c)

    {

        case '+':

            Result = a+b;

            break;

        case '-':

            Result = a-b;

            break;

        case '*':

            Result = a*b;

            break;

        case '/':

            Result = a/b;

            break;

        case '^':

            Result = pow(a,b);

            break;

        default:

            break;

    }

}

void GetResult(char str[],int length,double &Result)

{

    Result = 0;

    if( str == NULL || length<=0)  return ;

    STACKPD* stackpd = NULL;

    STACKPN* stackpn = NULL;

    NODEPN* value_b = NULL;

    NODEPN* value_a = NULL;

    NODEPD* value_c = NULL;

    NODEPN* insertnodepn = NULL;

    NODEPD *insertnodepd = NULL;

    InitStackPD(stackpd);

    InitStackPN(stackpn);

    int i=0;

    int sum ;

    int j;

    int k;

    double b;

    double a;

    char c;

    while(i<length){

        if(str[i]<='9' && str[i]>='0'){

            k=i;

            sum =0;

            j=0;

            while(k<length && str[k]<='9' && str[k]>='0'){

                sum = sum*10+(str[k]-'0');

                if(str[k+1] == '.'){

                    j = k+1;

                    k += 2;

                }

                else{

                    k++;

                }

            }

            i=k;

            insertnodepn = new NODEPN;

            if(j!=0){

                insertnodepn->value = (double)(sum/(pow(10,k-j-1)));

            }else{

                insertnodepn->value = (double)(sum);

            }

            insertnodepn->pNext = NULL;

            push_pn(stackpn,insertnodepn);

        }

        else{

            if(stackpd->pdTop){

                NODEPD* stackpdtop = NULL;

                top_pd(stackpd,stackpdtop);

                char c_rule = GetRel(stackpdtop->value,str[i],c_data,rule);

                if(c_rule != ' '){

                    switch(c_rule){

                        case '>':

                            top_pn(stackpn,value_b);

                            b = value_b->value;

                            pop_pn(stackpn);

                            top_pn(stackpn,value_a);

                            a = value_a->value;

                            pop_pn(stackpn);

                            top_pd(stackpd,value_c);

                            c = value_c->value;

                            pop_pd(stackpd);

                            Deal(a,c,b,Result);

                            insertnodepn = new NODEPN;

                            insertnodepn->value = Result;

                            insertnodepn->pNext = NULL;

                            push_pn(stackpn,insertnodepn);

                            if( stackpd->pdCount > 0 ){

                                top_pd(stackpd,value_c);

                                c = value_c->value;

                                int flag =0;

                                c_rule = GetRel(c,str[i],c_data,rule);

                                switch(c_rule){

                                case '>':

                                    top_pn(stackpn,value_b);

                                    b = value_b->value;

                                    pop_pn(stackpn);

                                    top_pn(stackpn,value_a);

                                    a = value_a->value;

                                    pop_pn(stackpn);

                                    top_pd(stackpd,value_c);

                                    c = value_c->value;

                                    pop_pd(stackpd);

                                    Deal(a,c,b,Result);

                                    insertnodepn = new NODEPN;

                                    insertnodepn->value = Result;

                                    insertnodepn->pNext = NULL;

                                    push_pn(stackpn,insertnodepn);

                                    insertnodepd = new NODEPD;

                                    insertnodepd->value = str[i];

                                    insertnodepd->pNext = NULL;

                                    push_pd(stackpd,insertnodepd);

                                    break;

                                case '<':

                                    flag = 1;

                                    insertnodepd = new NODEPD;

                                    insertnodepd->value = str[i];

                                    insertnodepd->pNext = NULL;

                                    push_pd(stackpd,insertnodepd);

                                    break;

                                case '=':

                                    pop_pd(stackpd);

                                    break;

                                }

                                if(flag == 1){

                                    break;

                                }

                            }

                            else{

                                insertnodepd = new NODEPD;

                                insertnodepd->value = str[i];

                                insertnodepd->pNext = NULL;

                                push_pd(stackpd,insertnodepd);

                            }

                            break;

                        case '<':

                            insertnodepd = new NODEPD;

                            insertnodepd->value = str[i];

                            insertnodepd->pNext = NULL;

                            push_pd(stackpd,insertnodepd);

                            break;

                        case '=':

                            pop_pd(stackpd);

                            break;

                    }

                }

            }

            else{

                insertnodepd = new NODEPD;

                insertnodepd->value = str[i];

                insertnodepd->pNext = NULL;

                push_pd(stackpd,insertnodepd);

            }

            i++;

        }

    }

    top_pn(stackpn,value_b);

    b = value_b->value;

    pop_pn(stackpn);

    top_pn(stackpn,value_a);

    a = value_a->value;

    pop_pn(stackpn);

    top_pd(stackpd,value_c);

    c = value_c->value;

    pop_pd(stackpd);

    Deal(a,c,b,Result);

}

int main()

{

    char str[100]={0};

    cin>>str;

    double Result;

    GetResult(str,strlen(str),Result);

    cout<<Result<<endl;

    system("pause");

    return 0;

}