[栈] 表达式求值-C语言-多位数求值

标签:   后缀表达式  表达式求值

【理论】https://blog.csdn.net/summer_dew/article/details/82048387
【代码说明】支持:2位以上的数字,四则运算和幂运算
使用的栈,是自己实现,封装在2 SqStack.h文件中的,可自己实现,也可以参照:https://blog.csdn.net/summer_dew/article/details/82051767
【结果】
测试:10*(1*(2+6/3)-1)+3^(3-1)+1+1-2# 结果为
这里写图片描述
这里写图片描述
这里写图片描述

// 顺序栈
// 顺序栈
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define SElemType int
#include"2 SqStack.h"

void visit(SElemType e) {
    printf("%d ",e);
}
void visit_optr(SElemType e) {
    printf("%c ",e);
}
void Show(SqStack *pOPTR, SqStack *pOPND,char c) {
    //printf("| 步骤 | 操作数栈OPND | 操作符栈OPTR | 输入字符 |\n");
    static int first = 1;
    if (first==1) {
        printf("当前扫描的字符\t数字栈\t符号栈\n");
        first++;
    }
    printf("%c\t",c);
    StackTraverse(*pOPND, &visit);printf(" \t");
    StackTraverse(*pOPTR, &visit_optr);
    printf("\n");
}
//将操作符转换成矩阵下标
int getIndex(char c) { 
    switch(c) {
    case '+': return 0;
    case '-': return 1;
    case '*': return 2;
    case '/': return 3;
    case '(': return 4;
    case ')': return 5;
    case '^': return 6;
    case '#': return 7;
    }
    return -1;
}
// 两个操作数比较
// c1>c2 TRUE
// c1<c2 FALSE
int compare_op(char c1,char c2) {
    char result;
    static char priorityMatrix[8][8] = 
    {  // +   -   *   /   (   )   ^   #
        {'<','<','<','<','>','<','<','>'}, //+
        {'<','<','<','<','>','<','<','>'}, //-
        {'>','>','<','<','>','<','<','>'}, //*
        {'>','>','<','<','>','<','<','>'}, ///
        {'>','>','>','>','>','>','>','>'}, //(
        {'<','<','<','<','=','<','<','>'}, //)
        {'>','>','>','>','>','<','>','>'}, //^
        {'<','<','<','<','<','<','<','='}  //#
    };
    // 转换下标
    int c1_index = getIndex(c1);
    int c2_index = getIndex(c2);
    // 矩阵
    result =  priorityMatrix[c1_index][c2_index];
    switch (result) {
    case '<' : return -1; // c1<c2
    case '>' : return 1; // c1>c2
    case '=' : return 0; // c1=c2错误情况
    }
    return 0;
}
int Operate(int S1,char OP,int S2) {
    switch (OP) {
    case '+':
        return S1+S2;
    case '-':
        return S1-S2;
    case '*':
        return S1*S2;
    case '/':
        return S1/S2;

    case '^':
        return (int)pow(S1,S2);
    }
    return 0;
}

//表达式求值:规定为整数,未检查异常
/* 测试数据:
10+11+12#
10*(1*(2+6/3)-1)+3^(3-1)+1+1-2#
 */
int main() {
    SqStack OPTR; //存放符号(操作符)
    SqStack OPND; //存放数值(操作数)
    char c; //每次获得的字符
    int num,S1,S2,result,tmp,OP; //存放数字
    //初始化
    InitStack(&OPTR);
    Push(&OPTR, '#');
    InitStack(&OPND);

    printf("请输入表达式:\n");
    c=getchar();
    num=0;
    while ( !StackEmpty(OPTR) ) {
        if (c>='0' && c<='9') { //数字
            num = num*10 + c-'0'; //保存数字

            Show(&OPTR, &OPND, c); //UI
            printf("\t\t\t\t【操作】是数字%d\n",num); //UI
        } else { //操作符
            if (num!=0) { //之前有数字
                Push(&OPND, num); //入栈
                printf("\t\t\t\t【操作】至此,前面的扫描中得到一个数字%d,入栈\n",num); //UI
                Show(&OPTR, &OPND, c); //UI
                num =0; //归为0
            }
            GetTop(OPTR, &OP); //取出操作符栈顶元素
            //与上一个符号比较优先级
            tmp = compare_op((char)c, (char)OP);
            printf("\t\t\t\t【操作】优先级比较:%c与%c\n",c,OP);
            if ( tmp==1 ) { //c>tmp
                Push(&OPTR, c); //压栈

                Show(&OPTR, &OPND, c); //UI
                printf("\t\t\t\t【操作】将符号%c压栈\n",c); //UI
            } else if ( tmp==-1 ){ //c<tmp
                Pop(&OPTR, &OP);
                Pop(&OPND, &S2); //先取出的是后面一位的数字 
                Pop(&OPND, &S1);
                result = Operate(S1, (char)OP, S2);
                Push(&OPND, result);

                Show(&OPTR, &OPND, c); //UI
                printf("\t\t\t\t【操作】进行计算%d%c%d=%d,将结果压栈\n",S1,OP,S2,result);//UI

                continue; //不执行c=getchar(),当前的c还没有处理完
            } else if (tmp==0){
                // 1. c=) OP=(
                // 2. c=# OP=#
                Pop(&OPTR,&tmp); //将栈顶删除

                Show(&OPTR, &OPND, c); //UI
                printf("\t\t\t\t【操作】当前操作符和栈顶操作符相同,删除栈顶操作符\n");
            }

        }
        c = getchar();
    }
    GetTop(OPND,&result);
    printf("\n计算结果:%d\n", result);
    return 0;
}
原文链接:加载失败,请重新获取