中缀表达式转后缀表达式-阿里云开发者社区

中缀表达式转后缀表达式并计算结果

1. 话不多说,先上镇楼图
在这里插入图片描述
2.要实现中缀到后缀的转换

1.如果是数字,直接存入缓冲数组
2.如果是运算符直接入栈(注意优先级)
 3.当前入栈字符优先级高于栈顶字符优先级(或者当前栈为空)则直接入栈
4.当前入栈字符优先级低于栈顶字符优先级,则需要出栈栈顶元素(出栈的字符存入缓冲数组),直到当前入栈字符优先级高于栈顶字符优先级
5.左括号"(" ,在栈外默认优先级最高,入栈后默认优先级最低
6.遇到右括号")",则依次弹出栈顶元素直至弹出左括号")"

3.实现前的一些准备

1.创建一个全局缓冲字符数组用来存储转换过程中的字符以及数字

char buffer[SIZE] = { 0 };   //存储缓冲

2.创建一个让字符存入缓冲的函数Put

//字符存入
void Put(char ch)
{
    static int index = 0; //静态变量
    buffer[index++] = ch;
}

3.设置运算符的优先级

//设置优先级
int Priority(char ch)
{
    int ret = 0;
    switch (ch)
    {
    case '+':
    case '-':
        ret = 1;
        break;
    case '*':
    case '/':
        ret = 2;
        break;
    default:
        break;
    }
    return ret;
}

4.判断是否是左括号,右括号

//是左括号
int isLeft(char ch)
{
    return ch == '(';
}
//是右括号
int isRight(char ch)
{
    return ch == ')';
}

5.判断是否是运算符

//是否是运算符
int isOperator(char ch)
{
    return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}

6.判断是否是数字

//是否是数字
int isNumber(char ch)
{
    return (ch >= '0' && ch <= '9');
}

7.实现中缀向后缀的转换

//中缀转后缀  正确返回Correct  错误返回Error
int transForm(const char* str)
{
    //创建一个数组栈
    char stack[SIZE];
    //初始化栈中数据
    memset(stack, 0, sizeof(char)*SIZE);
    int top = -1;
    //遍历字符
    while (*str)
    {
        //判断是否为数字,是数字直接存入buffer
        if (isNumber(*str))
        {
            Put(*str);  //存入buffer
        }
        else if (isOperator(*str))   //判断是否为运算符
        {
//比较栈顶字符与入栈字符的优先级  需要弹出所有的栈顶元素大于入栈字符的元素
//top!=-1 表示栈不为空
            while (top != -1 && Priority((char)stack[top]) >= Priority(*str))
            {
                    //1.入栈字符优先级低于栈顶元素,出栈栈顶元素存入buffer
                    Put((char)stack[top--]);
            }
            //2.入栈字符优先级高于栈顶元素直接入栈或者 空栈直接入栈
            stack[++top] = *str;  //入栈
        }
        else if (isLeft(*str))   //左括号 直接入栈
        {
            stack[++top] = *str;  //入栈
        }
        else if (isRight(*str))  //右括号
        {
            //栈空返回Error
            if (top == -1)
            {
                printf("栈中数据读取错误!\n");
                return Error;
            }
            //栈顶元素不是左括号
            while (!isLeft((char)stack[top]))
            {
                //不是左括号出栈栈顶元素 并保存至缓冲数组中
                Put((char)stack[top--]);
                //没有找到
                //没有对应的左括号与右括号匹配
                if (top == -1)
                {
                    printf("未找到左括号!\n");
                    return Error;
                }
            }
            //找到左括号将左括号弹出
            stack[top--];
        }
        else
        {
            printf("有不能识别的字符!\n");
            return Error;
        }
        str++;
    }
    //遍历结束,弹出栈中的剩下的所有元素
    if (*str == '\0')
    {
        while (top !=-1)
        {
        //如果还有左括号未跟右括号匹配则返回Error
            if (isLeft((char)stack[top]))
            {
                printf("还存在没有匹配的\"(\"没有\")\"匹配\n");
                return Error;
            }
            //出栈栈中元素并存入缓冲
            Put((char)stack[top--]);
        }
    }
    else
    {
        printf("遍历没有完成!\n");
            return Error;
    }
    return Correct;
}

8.如何实现后缀表达式的计算??

遍历后缀表达式
如果是数字就入栈
如果是运算符就出栈栈中的两个数字(左操作数与右操作数)做运算
计算结果入栈继续上述操作,直至栈空

9.实现后缀表达式的计算

//传入字符并返回运算结果
int express(int left, int right, char op)
{
    switch (op)
    {
    case '+':
        return left + right;
    case '-':
        return left - right;
    case '*':
        return left * right;
    case '/':
        return left / right;
    default:
        break;
    }
    return -1;
}
//后缀表达式的计算
int calculatePosture(const char* str)
{
    //创建一个空栈
    int stack[SIZE] = { 0 };
    int top = -1;
    //保存计算后的结果
    int ret = 0;
    //遍历字符串
    while (*str)
    {
        //如果是数字字符直接入栈
        if (isNumber(*str))
        {
            //将字符转换为数字后再入栈
            stack[++top] = *str - '0';
        }
        //如果是运算符
        else if (isOperator(*str))
        {
        //栈不为空
            if (top == -1)
            {
                printf("栈中数据错误!\n");
                break;
            }
            //出栈栈中数字
            int left = stack[top--];
            int right = stack[top--];
            //做运算
            ret = express(left, right, *str);
            //运算结果入栈
            stack[++top] = ret;
        }
        else
        {
            printf("后缀表达式有误!\n");
            break;
        }
        //指针偏移
        str++;
        //遍历结束并且栈中仅有一个元素
        //返回栈中计算结果
        if (!(*str) && top == 0)
            return ret;
    } 
}

10.整体代码

#include<stdio.h>
#include<stdlib.h>
#define SIZE 1024
#define Error 0
#define Correct 1

char buffer[SIZE] = { 0 };   //存储缓冲
//字符存入
void Put(char ch)
{
    static int index = 0; //静态变量
    buffer[index++] = ch;
}
//设置优先级
int Priority(char ch)
{
    int ret = 0;
    switch (ch)
    {
    case '+':
    case '-':
        ret = 1;
        break;
    case '*':
    case '/':
        ret = 2;
        break;
    default:
        break;
    }
    return ret;
}
//是左括号
int isLeft(char ch)
{
    return ch == '(';
}
//是右括号
int isRight(char ch)
{
    return ch == ')';
}
//是否是运算符
int isOperator(char ch)
{
    return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}
//是否是数字
int isNumber(char ch)
{
    return (ch >= '0' && ch <= '9');
}
//中缀转后缀  正确返回Correct  错误返回Error
int transForm(const char* str)
{
    //创建一个栈
    char stack[SIZE];
    memset(stack, 0, sizeof(char)*SIZE);
    int top = -1;
    //遍历字符
    while (*str)
    {
        //判断是否为数字,是数字直接存入buffer
        if (isNumber(*str))
        {
            Put(*str);  //存入buffer
        }
        else if (isOperator(*str))   //判断是否为运算符
        {
            //比较栈顶元素与新字符的优先级  需要弹出所有的栈顶元素大于新字符的元素
            while (top != -1 && Priority((char)stack[top]) >= Priority(*str))
            {
            //1.新字符优先级低于栈顶元素,出栈栈顶元素存入buffer
                    Put((char)stack[top--]);
            }
            //2.新字符优先级高于栈顶元素直接入栈或者 空栈
            stack[++top] = *str;  //入栈
        }
        else if (isLeft(*str))   //左括号 入栈
        {
            stack[++top] = *str;  //入栈
        }
        else if (isRight(*str))  //右括号
        {
            //判断栈顶是否为左括号,不是就弹出,直到找到左括号
            if (top == -1)
            {
                printf("栈中数据读取错误!\n");
                return Error;
            }
            while (!isLeft((char)stack[top]))
            {
                //不是左括号出栈 并保存
                Put((char)stack[top--]);
                //没有找到
                if (top == -1)
                {
                    printf("未找到左括号!\n");
                    return Error;
                }
            }
            //找到左括号弹出
            stack[top--];
        }
        else
        {
            printf("有不能识别的字符!\n");
            return Error;
        }
        str++;
    }
    //遍历结束,弹出栈中的所有元素
    if (*str == '\0')
    {
        while (top !=-1)
        {
            if (isLeft((char)stack[top]))
            {
                printf("还存在没有匹配的\"(\"没有\")\"匹配\n");
                return Error;
            }
            Put((char)stack[top--]);
        }
    }
    else
    {
        printf("遍历没有完成!\n");
            return Error;
    }
    return Correct;
}

//后缀表达式的计算
int express(int left, int right, char op)
{
    switch (op)
    {
    case '+':
        return left + right;
    case '-':
        return left - right;
    case '*':
        return left * right;
    case '/':
        return left / right;
    default:
        break;
    }
    return -1;
}
int calculatePosture(const char* str)
{
    //创建一个空栈
    int stack[SIZE] = { 0 };
    int top = -1;
    //保存计算后的结果
    int ret = 0;
    //遍历字符串
    while (*str)
    {
        //如果是数字直接入栈
        if (isNumber(*str))
        {
            //入栈是将字符转换为数字
            stack[++top] = *str - '0';
        }
        //如果是运算符
        else if (isOperator(*str))
        {
            if (top == -1)
            {
                printf("栈中数据错误!\n");
                break;
            }
            //出栈数字
            int left = stack[top--];
            int right = stack[top--];
            //做运算
            ret = express(left, right, *str);
            //运算结果入栈
            stack[++top] = ret;
        }
        else
        {
            printf("后缀表达式有误!\n");
            break;
        }
        //指针偏移
        str++;
        //遍历结束并且栈中仅有一个元素
        //返回栈中计算结果
        if (!(*str) && top == 0)
            return ret;
    } 
}
int main()
{
    system("color F0");
    char str[SIZE] = { 0 };
    printf("请您输入您想转换的中缀表达式!\n");
    scanf("%s", str);
    if (transForm(str) == Error)
    {
        printf("出现错误,转换失败!\n");
    }
    else
        printf("转换后的后缀表达式为: %s\n", buffer);
    //后缀表达式的计算
    int answer = calculatePosture(buffer);
    printf("运算结果为: %d\n", answer);

    system("pause");
    return 0;
}

11.运行示例
okok

中缀表达式转后缀表达式

中缀表达式转后缀表达式并计算结果

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

中缀表达式转后缀表达式

中缀表达式转后缀表达式并计算结果

热门文章

最新文章

相关电子书