手机版
你好,游客 登录 注册
背景:
阅读新闻

逆波兰表达式 - 中缀表达式转后缀表达式

[日期:2019-08-02] 来源:Linux社区  作者:lanhaicode [字体: ]

逆波兰表达式

先说一下中缀表达式,平时我们使用的运算表达式就是中缀表达式,例如1+3*2,中缀表达式的特点就是:二元运算符总是置于与之相关的两个运算对象之间

人读起来比较好理解,但是计算机处理起来就很麻烦,运算顺序往往因表达式的内容而定,不具规律性

 

后缀表达式,后缀表达式的特点就是:每一运算符都置于其运算对象之后,以上面的中缀表达式1+2*3为例子,转为后缀表达式就是123*+

 

下面先分析怎么把中缀表达式转换为后缀表达式,这里我们考虑六种操作符'+'、'-'、'*'、'/'、'('、')',完成中缀转后缀我们需要两个数组,都以栈的方式来操作,一个数组用来存放后缀表达式(char num[100]),

一个数组用来临时存放操作数(char opera[100])(这里说临时存放,是因为最后都要入栈到后缀表达式数组num中,这个数组就相当于一个中转站)

 

1、从左往右扫描中缀表达式(这里我们以1*(2+3)为例)

 

2、如果是数字那么将其直接入栈到数组num

3、如果是操作数,需要进一步判断

(1)如果是左括号'('直接入栈到数组opera

(2)如果是运算符('+'、'-'、'*'、'/'),先判断数组opera栈顶的操作数的优先级(如果是空栈那么直接入栈到数组opera),如果是左括号那么直接入栈到数组opera中,如果栈顶是运算符,且栈顶运算符的优先级大于该运算符

那么将栈顶的运算符出栈,并入栈到数组num中,重复步骤3,如果栈顶运算符优先级小于该运算符,那么直接将该运算符入栈到opera中

(3)如果是右括号')',那么说明在opera数组中一定有一个左括号与之对应(在你没输错的情况下),那么将opera中的运算符依次出栈,并入栈到num中,直到遇到左括号'('(注意左括号不用入栈到num

4、如果中缀表达式扫描完了,那么将opera中的操作数依次出栈,并入栈到num中就可以了,如果没有没有扫描完重复1-3步

上面就是中缀表达式转后缀表达式的步骤了,下面用图来直观的了解一下这个过程

 

需要注意的是:opera中操作数,越靠近栈顶,优先级越高,下面附上实现代码

void PexpretoSexpre(char *ss)
{
    char num[100] = "0";    /* 存储后缀表达式 */
    char opera[100] = "0";    /* 存储运算符 */
    /*
    num----j
    opera----op
    ss----i
    */
    int i, j, op;

    op = i = j = 0;

    while (ss[i] != '\0')
    {
        if (isdigit(ss[i]))    /* 如果是数字 */
        {
            num[j] = ss[i];    /* 数字直接入后缀表达式栈 */
            j++;
            i++;
        }
        else
        {
            switch (ss[i])    /* 如果是操作数 */
            {
            case '+':
                {
                    if (op == 0)    /* 如果是空栈 */
                    {
                        PushOperation(opera, ss, &op, &i);    /* 入运算符栈 */
                        break;
                    }
                    if (opera[op-1] == '+' || opera[op-1] == '-' || opera[op-1] == '*' || opera[op-1] == '/' || opera[op-1] == ')' || opera[op-1] == '(')
                    {
                        switch (opera[op-1])
                        {
                        case '+':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        case '-':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        case '*':
                            {    /* 加法优先级低于乘法 */
                                num[j] = opera[op-1];    /* 将操作数出栈 */
                                opera[op-1] = ss[i];        /* 将新的操作数压入栈中 */
                                j++;
                                i++;
                                break;
                            }
                        case '/':
                            {
                                num[j] = opera[op-1];
                                opera[op-1] = ss[i];
                                j++;
                                i++;
                                break;
                            }
                        case '(':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        }
                    }
                    break;
                }
            case '-':
                {
                    if (op == 0)
                    {
                        PushOperation(opera, ss, &op, &i);
                        break;
                    }
                    if (opera[op-1] == '+' || opera[op-1] == '-' || opera[op-1] == '*' || opera[op-1] == '/' || opera[op-1] == ')' || opera[op-1] == '(')
                    {
                        switch (opera[op-1])
                        {
                        case '+':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        case '-':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        case '*':
                            {
                                num[j] = opera[op-1];
                                opera[op-1] = ss[i];
                                j++;
                                i++;
                                break;
                            }
                        case '/':
                            {
                                num[j] = opera[op-1];
                                opera[op-1] = ss[i];
                                j++;
                                i++;
                                break;
                            }
                        case '(':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        }
                    }
                    break;
                }
            case '*':
                {
                    if (op == 0)
                    {
                        PushOperation(opera, ss, &op, &i);
                        break;
                    }
                    if (opera[op-1] == '+' || opera[op-1] == '-' || opera[op-1] == '*' || opera[op-1] == '/' || opera[op-1] == ')' || opera[op-1] == '(')
                    {
                        switch (opera[op-1])
                        {
                        case '+':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        case '-':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        case '*':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        case '/':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        case '(':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        }
                    }
                    break;
                }
            case '/':
                {
                    if (op == 0)
                    {
                        PushOperation(opera, ss, &op, &i);
                        break;
                    }
                    if (opera[op-1] == '+' || opera[op-1] == '-' || opera[op-1] == '*' || opera[op-1] == '/' || opera[op-1] == ')' || opera[op-1] == '(')
                    {
                        switch (opera[op-1])
                        {
                        case '+':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        case '-':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        case '*':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        case '/':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        case '(':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
                            }
                        }
                    }
                    break;
                }
            case '(':
                {
                    PushOperation(opera, ss, &op, &i);
                    break;
                }
            case ')':    /* 如果遇到右括号 */
                {
                    while (opera[op-1] != '(')
                    {
                        num[j] = opera[op-1];    /* 将运算符栈中的元素依次入栈到后缀表达式栈中,直到遇到左括号为止 */
                        j++;
                        op--;
                    }
                    op--;
                    i++;
                    break;
                }
            default:
                {
                    printf("传入表达式不符合要求\n");
                    exit(0);
                }
                   
            }
        }
    }
    while (op != 0)
    {
        num[j] = opera[op-1];    /* 将运算符栈中的元素依次入栈到后缀表达式栈中 */
        j++;
        op--;
    }
    num[j] = '\0';
    i = 0;
    while (num[i] != '\0')    /* 将后缀表达式存储到传入的形参ss中 */
    {
        ss[i] = num[i];
        i++;
    }
    ss[i] = '\0';
}

/* Function: 入运算符栈*/
void PushOperation(char *opera, char *ss, int *op, int *s)
{
    opera[*op] = ss[*s];
    (*op)++;
    (*s)++;
}

后缀表达式的计算

完成了中缀表达式转后缀表达式,接下来就是后缀表达式的计算了,后缀表达式的计算比中缀转后缀要稍微简单一点,只需要对我们转换好的后缀表达式从左往右依次扫描,并依次入栈就行了,

意思是只需要用一个数组(double num[100])就OK了

需要考虑的情况如下

1、如果是数字,那么直接入栈到num中

2、如果是运算符,将栈顶的两个数字出栈(因为我们考虑的运算符加、减、乘、除都是双目运算符,只需要两个操作数),出栈后对两个数字进行相应的运算,并将运算结果入栈

3、直到遇到'\0'

下面用几张图,来直观了解下这个过程,以上面转换好的后缀表达式"123+*"为例(这里用ss来存储后缀表达式,num来存储计算结果,注意不要与上面图中num搞混淆了)

 

 

(注意:这里将计算结果5入栈后,栈顶从之前的[3]变成[2])

到这里后缀表达式的计算就结束了,下面附上实现代码

 

#include <stdio.h>
#include <stdlib.h>

 

#define MAX 100

 

void JudgeFopen_s(errno_t err);        /* 判断文件打开是否成功 */
void ReadFile(FILE *fp, char *ss);    /* 读取文件内容 */
double TransformCtoD(char ch);        /* 将char类型数组的每一个元素转换为double */
void CalculateAndPush(double *num, int *i, int *j, char mm);    /* 计算结果并入栈 */

 

int main()
{
    FILE *fp;
    errno_t err;

 

    char ss[MAX];    /* 存储逆波兰表达式 */
    int i = 0;
    int j = 0;
    double num[MAX];    /* 栈 */
   
    err = fopen_s(&fp, "E:\\ww.txt", "r");

 

    JudgeFopen_s(err);    /* 判断文件打开是否成功 */
    ReadFile(fp, ss);    /* 读取文件内容,存储到ss中*/

 

    while (ss[i] != '\0')
    {
        if (ss[i] >= '0' && ss[i] <= '9')    /* 如果是数字 */
        {
            /* 因为num是char类型的,需要转换为double类型方便计算 */
            num[j] = TransformCtoD(ss[i]);    /* 将数字存储到栈中 */
            j++;
            i++;
        }
        else if (ss[i] == '+' || ss[i] == '-' || ss[i] == '*' || ss[i] == '/')
        {
            CalculateAndPush(num, &i, &j, ss[i]);    /* 计算结果并入栈 */
        }
        else if (ss[i] == '\n')    /* 如果是换行符,结束循环*/
        {
            break;
        }
    }

 

    printf("%lf", num[0]);

 

    return 0;
}

 

/* Function: 计算结果并入栈 */
void CalculateAndPush(double *num, int *i, int *j, char mm)
{
    switch (mm)
    {
    case '+':
        {
            num[(*j)-2] = num[(*j)-1] + num[(*j)-2];
            (*j)--;
            (*i)++;
            break;
        }
    case '-':
        {
            num[(*j)-2] = num[(*j)-1] - num[(*j)-2];
            (*j)--;
            (*i)++;
            break;
        }
    case '*':
        {
            num[(*j)-2] = num[(*j)-1] * num[(*j)-2];
            (*j)--;
            (*i)++;
            break;
        }
    case '/':
        {
            num[(*j)-2] = num[(*j)-1] / num[(*j)-2];
            (*j)--;
            (*i)++;
            break;
        }
    default:
        {
            exit(0);
        }
    }
}
/* Function: 判断文件打开是否成功 */
void JudgeFopen_s(errno_t err)
{
    if (err != 0)
    {
        printf("文件打开失败\n");
        system("pause");
        exit(0);
    }
}

 

/* Function: 读取文件内容*/
void ReadFile(FILE *fp, char *ss)
{
    int i = 0;

 

    while (!feof(fp))
    {
        fscanf_s(fp, "%c", &ss[i]);
        i++;
    }
    ss[i-1] = '\0';
}

 

/* Function: 将char类型数组的每一个元素转换为double */
double TransformCtoD(char ch)
{
    return (double)(ch - '0');
}

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址https://www.linuxidc.com/Linux/2019-08/159753.htm

linux
相关资讯       逆波兰表达式  中缀表达式  后缀表达式 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款