使用栈计算表达式

设计思想

本题中规定的功能涉及的算法有：中缀表达式求值、将中缀表达式转换为后缀表达式、后缀表达式求值。

1. 中缀表达式求值

• 首先定义两个栈，分别用于存取运算符和运算数。
• 然后依次读取表达式的一个字符ch，如果ch是数值，入数值栈

• 如果ch是运算符，把它与符号栈的栈顶元素的优先级比较：

  • 若“<”即优先级低:该运算符进栈，读入下一个字符；
  • 若“>”即优先级高，从运算符栈退出一个运算符，从运算数栈里退出两个运算数进行运算，并将结果入运算数栈。
  • 若“=”即优先级相等(一般用于“（）”的判定):运算符退栈，消去一个括号读入下一个字符;
  • 这时需用到比较运算符优先级的函数：precede(w,ch)
• 重复上述过程，直至整个表达式求值完毕（即符号栈的栈顶元素和当前读入的字符均为”#”），操作数栈的栈顶元素为计算结果。

2. 将中缀表达式转换为后缀表达式

• 从左向右读取表达式，读到运算数把它输出；

• 读到运算符f，则把符号栈的栈顶元素的算符和f进行优先级比较：

  • 若优先级高:该运算符入运算符栈；
  • 若优先级相等:从运算符栈退出一个运算符，不输出;
  • 若优先级低，从运算符栈退出一个运算符，从运算数栈里输出所有比f优先级高的运算符，直至栈顶算符优先级小于f，f入运算符栈。
• 重复以上流程，一直到最终输出后缀表达式为止。

算法流程图

表达式求值算法流程图.png

源代码

#include <stdio.h>

#define StackSize 100

/* 定义字符栈 */

typedef char ElemType;

typedef struct{
    ElemType  data[StackSize];
    int top;
}SqStack;

/* 定义数值栈 */

typedef struct {
    double  data[StackSize];
    int top;
}dstack;

/* 初始化数值栈 */

void  DsInit(dstack *s){    
    s->top = -1;
}

/* 压栈 */

int Dpush(dstack *s, double e){

    if (s->top < StackSize - 1){
        s->top = s->top + 1;/*若栈不满，则将e进栈*/
        s->data[s->top] = e;
        return 1;
    }else{    
        return 0;
    }
}

/* 出栈 */

double Dpop(dstack *s){
    double e;
    if (-1 == s->top){    
        return 1;
    }else{    
        e = s->data[s->top];/*出栈*/    
        (s->top)--;
        return e;
    }
}

/* 初始化字符栈 */

void  InitStack(SqStack *s){
    s->top = -1;
}

/* 压栈 */

int push(SqStack *s, ElemType e){
    if (s->top < StackSize - 1){
        s->top = s->top + 1;
        s->data[s->top] = e;
        return 1;
    }else{
        return 0;
    }
}

/* 出栈 */

ElemType pop(SqStack *s){

    ElemType e;
    if (-1 == s->top){
        return 1;
    }else{
        e = s->data[s->top];
        (s->top)--;
        return e;
    }
}

/* 取栈顶 */

int GetTop(SqStack s, ElemType *e){

    if (0 == s.top){
        *e = s.data[s.top];
        return 0;
    }else{
        *e = s.data[s.top];
        return 1;
    }
}

/* 比较优先级 */

int Get_Pri(int mode, char oper){

/* 返回运算符oper代表优先级得整数值，mode为1，表示oper是栈顶运算符，否则是当前运算符 */

    int tmp;
    switch (oper){
    case '#': tmp = 0; break;
    case '(': tmp = (mode ? 1 : 6); break;
    case '+':
    case '-': tmp = (mode ? 3 : 2); break;
    case '*':
    case '%':
    case '/': tmp = (mode ? 5 : 4); break;
    case ')': tmp = (mode ? 7 : 1); break;
    }
    return tmp;
}

char precede(char w, char ch){

/* 判定运算符栈的栈顶运算符w,与当前运算符ch之间的优先关系 */

    int grade;

    /* 取得栈顶运算符与当前运算符得优先级 */

    grade = Get_Pri(1, w) - Get_Pri(0, ch);
    if (grade > 0){
        return '>';
    }else {
        if (grade == 0){
            return '=';
        }else {
            return '<';
        }
    }
}

/* 中缀变后缀的实现函数 */

void change(char E[], char A[]){

    SqStack S2;
    int i = 0; /*i作为扫描数组E的指针*/
    int j = 0;    /*j用来指示数组A中待写入字符的位置*/
    int k = 0; /*标识上一位是否为'('*/

    char ch = E[i];   /*E中第一个字符送给ch*/
    char w = '\0';   /*字符串结束字符*/

    InitStack(&S2);
    push(&S2, '#'); /*栈顶压入'#',以表示空栈*/

    while (ch != '#'){ /*判断是否读取到表达式结束标记*/
        if (ch >= '0' && ch <= '9' || ch == '.'){ /*数字处理方案*/
            k = 0;
            while (ch >= '0' && ch <= '9' || ch == '.'){
                A[j] = ch;  
                j++;
                i++;
                ch = E[i];  /*E中下一个字符送给ch*/
            }
            A[j] = ' ';
            j++;    /*给A中的每个操作数后附加一个空格*/
        }
        if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '%' || ch == '(' || ch == ')' || ch == '#'){
            if (ch == '(') {
                k = 1;
            }
            if (k == 1 && ch == '-') {/*负数处理*/
                A[j] = '0';
                j++;/*给A中的负数前附加一个0*/
                A[j] = ' ';
                j++;    /*给A中的每个操作数后附加一个空格*/
            }        
            GetTop(S2, &w); /* 字符栈取栈顶 */
            while (precede(w, ch) == '>'){/*比较优先级*/
                A[j] = w; 
                j = j + 1;
                pop(&S2);/* 字符栈出栈 */
                GetTop(S2, &w);
            }
            if (precede(w, ch) == '<') {
                push(&S2, ch); /* 字符栈压栈 */
            }else{
                if (precede(w, ch) == '='&&w != '#'){
                    pop(&S2);
                    GetTop(S2, &w);
                }
            }
        }
        if (E[i] != '#') { /*空格处理*/
            i++;
        }
        ch = E[i];
    }

    while (w != '#'){
        A[j] = w;
        j++;
        pop(&S2);
        GetTop(S2, &w);
    }
    A[j] = '#';/*结束处理*/
    A[++j] = '\0';
}

/* 计算后缀表达式的值 */

double comp(char arr[]){
    dstack s;
    int i = 0;
    char ch;
    double x = 0, d = 1.0;
    DsInit(&s);
    ch = arr[i];
    while (ch != '#'){
        switch (ch){
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
        case '.':
            while (ch != ' '){
                if ('0' <= ch && ch <= '9'){
                    while ('0' <= ch && ch <= '9'){
                        x = x * 10 + (ch - '0');
                        i = i + 1;
                        ch = arr[i];
                    }
                }else{
                    if (ch == '.'){
                        ch = arr[++i];
                        while ('0' <= ch && ch <= '9'){
                            d = d * 10;
                            x = x + (ch - '0') / d;
                            ch = arr[++i];
                        }
                    }
                }
            }
            break;
        case '+':
            x = Dpop(&s) + Dpop(&s);
            break;
        case '-':
            x = Dpop(&s);
            x = Dpop(&s) - x;
            break;
        case '*':
            x = Dpop(&s)*Dpop(&s);
            break;
        case '/':
            x = Dpop(&s);
            x = Dpop(&s) / x;
            break;
        case '%':
            x = Dpop(&s);
            x = (double)((int)Dpop(&s) % (int)x);
            break;
        }
        Dpush(&s, x);
        x = 0;
        i = i + 1;
        ch = arr[i];
    }
    return Dpop(&s);
}

/* 主函数 */

void main(){
    char E[100];
    char A[100];
    printf("请输入表达式并以'#'结束,负数请用'()'标记：");
    gets(E);
    system("cls");/*清屏*/
    change(E, A);
    printf("中缀表达式：%s \n", E);
    printf("后缀表达式：%s \n", A);
    printf("最终结果：%s=%f \n \n", E, comp(A));
    system("pause");/*暂停运行,以显示结果*/
    system("cls");
    main();
}

运行结果

表达式求值算法运行结果.png

遇到的问题及解决

问题1：忽略了变量的类型，进行了不合法的运算，程序出现异常。

解决方法：严格检查变量类型，养成每次调用变量前先查看变量定义再使用变量的好习惯。

问题2：书写标识符时，忽略了大小写字母的区别，导致程序出现未知错误。

解决方法：后来发现在运行时候左下角会出现“半”，括号是在中文环境下输入的括号，改成英文下的出现正确结果。

问题3：操作数和运算符在一起发生冲突，当混合输入数据和运算符，出现异常，没有结果。

解决方法：使用两个工作栈，一个存储数字，一个存储运算符。

问题4：操作数和运算符在一起发生冲突，当混合输入数据和运算符，出现异常，没有结果。

解决方法：使用两个工作栈，一个存储数字，一个存储运算符。