栈在表达式计算过程中的应用

谁践踏了优雅 2022-05-17 05:36 119阅读 0赞

**栈在表达式计算过程中的应用** ：建立操作数栈和运算符栈。运算符有优先级。  
**规则**：  
自左至右扫描表达式，凡是遇到操作数一律进操作数栈。  
当遇到运算符时，如果它的优先级比运算符栈栈顶元素的优先级高就进栈。反之，取出栈顶运算符和操作数栈栈顶的连续两个操作数进行运算，并将结果存入操作数栈，然后继续比较该运算符与栈顶运算符的优先级。  
左括号一律进运算符栈，右括号一律不进运算符栈，取出运算符栈顶运算符和操作数栈顶的两个操作数进行运算，并将结果压入操作数栈，直到取出左括号为止。

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAX  100
    
    enum link{PUSH, PUSH_NO};
    
    typedef struct      // 运算数
    {
        int num[MAX];
        int top;
    }OP_num;
    
    typedef struct      // 运算符
    {
        char str[MAX];
        int top;
    }OP_ch;
    
    // 运算数置空栈
    void SETNULL_num (OP_num* s)        
    {
        s->top = -1;
    }
    
    // 运算符置空栈
    void SETNULL_ch (OP_ch* s)
    {
        s->top = -1;
    }
    
    // 判断是否是数字，是返回1 不是返回0
    int is_num (char ch)    
    {
        if (ch >= '0' && ch <= '9')
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }       
    
    // 数字入栈
    int PUSH_num (OP_num *s, int data)
    {
        if ((MAX - 1) == s->top)
        {
            return 0;
        }
        else
        {   
            s->num[++s->top] = data;
        }
    }
    
    // 运算符入栈
    int PUSH_ch (OP_ch* s, char ch)
    {
        if ((MAX - 1) == s->top)
        {
            return 0;
        }
        else
        {
            s->str[++s->top] = ch;
        }
    }
    
    // 判断是否将运算符入栈
    int jud (OP_ch* s, char ch)
    {
        if (-1 == s->top)   // 判断是否是空栈
        {
            return PUSH;
        }
        else
        {
            switch (s->str[s->top])     // 根据栈顶运算判断是否进栈
            {
                case '+':           //  当栈顶是'+-'时，只有‘+-）’不进栈
                case '-':
                {
                    if (ch == '+' || ch == '-' || ch == ')')
                    {
                        return PUSH_NO;
                    }
                    else
                    {
                        return PUSH;
                    }
                    break;
                }
                case '*':
                case '/':
                {
                    if ('(' == ch)
                    {
                        return PUSH;
                    }
                    else
                    {
                        return PUSH_NO;
                    }
                    break;
                }
                case '(':
                {
                    return PUSH;
                    break;
                }
            }
        }
    }
    
    
    // 数字出栈
    int Pop_num (OP_num* s)
    {
        return (s->num[s->top--]);
    }
    
    // 运算符出栈
    void Pop_ch (OP_ch* s)
    {
        s->top--;
    }
    
    // 进行运算
    void operate (OP_ch* s_ch, OP_num* s_sum)
    {
        int a = Pop_num(s_sum);                     // 取第一个数
        int b = Pop_num(s_sum);                     // 取第二个数
        int result;
    
        // 根据当前运算符栈顶的符号来判断进行何种运算
        switch (s_ch->str[s_ch->top])
        {
            case '+':
                result = a + b;
                break;
            case '-':
                result = b - a;
                break;
            case '*':
                result = a * b;
                break;
            case '/':
                result = b / a;
                break;
        }   
        PUSH_num (s_sum, result);                   // 将运算结果入栈
    }
    
    int main()
    {
        OP_num sdata;
        OP_ch  soper;
    
        SETNULL_num (&sdata);
        SETNULL_ch  (&soper);
    
        int i = 0, len_str, t;
    
        char str[MAX];
        char str_num[MAX];          // 存放要转化的数字
        gets (str);                 // 输入表达式
        len_str = strlen (str);     // 获取表达式长度
    
        while (str[i] != '\0')      // 遍历表达式
        {
            if (is_num(str[i]))     // 判断是否是数字
            {
                t = 0;
                while (is_num(str[i]))
                {
                    str_num[t++] = str[i++];
                    //将表达式中的数字进行保存，用于转化为对应的整形数
                }
                str_num[t] = '\0';
                PUSH_num (&sdata, atoi(str_num));
                // 遇到算数符号的时候让符号前面的数进栈
            }
            else
            {
                if (PUSH == jud(&soper, str[i]))
                {
                    PUSH_ch (&soper, str[i]);
                }
                else
                {
                    if (str[i] != ')')      // ')'不让其入栈所以单独列出来讨论
                    {
                        operate (&soper, &sdata);       // 进行一次运算并一处栈顶运算符
                        Pop_ch(&soper);                 // 符号出栈
                        PUSH_ch (&soper, str[i]);       // 进行压栈
                        // 相当于用当前的运算符替换了刚才栈顶的运算符号
                    }
                    else                // 遇到')'
                    // 不断取字符运算 知道遇到 ')'
                    {
                        do
                        {
                            operate (&soper, &sdata);
                            Pop_ch (&soper);
                        }while (soper.str[soper.top] != '(');
    
                        Pop_ch (&soper);
                        // 将‘（’弹出栈空间
                    }
                }
                i++;
            }
        }
        while (soper.top != -1)
        {
            operate (&soper, &sdata);
            Pop_ch (&soper);
        }
        printf ("%d\n", sdata.num[sdata.top]);
    
        return 0;
    }