C语言实现中缀表达式转后缀表达式并计算

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

#define MAXSIZE 100

/*
  操作符栈的基本规则:
  读入一个操作符时，弹出栈顶元素直至发现优先级更低的元素为止。
  除非是在处理一个'）'，否则绝不从栈中弹出'（'。遇到'）'，
  将栈顶元素弹出并输出直到遇到相应的'（'，但该'（'只弹出，不输出。
  读入输入的末尾时，若栈非空，依此弹出并输出所有栈元素。
*/

//字母栈的结构
typedef struct CharacterStack {
    //栈数组
    char arr[MAXSIZE];

    //栈顶位置
    int top;
}Stackcs;

//数字栈的结构
typedef struct NumberStack {
    //数字数组
    int brr[MAXSIZE];

    //栈顶位置
    int top;
}Stackns;

//判断字母栈是否为空
int isEmpty(Stackcs* s)
{
    return (s->top == -1);
}

//判断数字栈是否为空
int isEmpty(Stackns* s)
{
    return (s->top == -1);
}

//字母栈顶元素
char topcs(Stackcs* s)
{
    //如果栈不为空
    if (!isEmpty(s)) {
        return s->arr[s->top];
    }
    return ' ';// 返回一个默认值，避免警告
}

//获取数字栈栈顶元素
int topns(Stackns* s)
{
    //如果栈不为空
    if (!isEmpty(s)) {
        return s->brr[s->top];
    }
    return 0;// 返回一个默认值，避免警告
}

//入字母栈
void pushcs(Stackcs* s, char c)
{
    s->arr[++s->top] = c;
}

//入数字栈
void pushns(Stackns* s, int val)
{
    s->brr[++s->top] = val;
}

//出字母栈
void popcs(Stackcs* s)
{
    s->top--;
}

//出数字栈
void popns(Stackns* s)
{
    s->top--;
}

//优先级函数
int getPriority(char operation)
{
    if (operation == '+' || operation == '-') {
        return 0;
    }
    else if (operation == '*' || operation == '/') {
        return 1;
    }
    else if (operation == '(' || operation == ')') {
        return 2;
    }
    else {
        return -1;
    }
}

//转化为后缀表达式
void toPostfix(char expression[], char postfix[])
{
    Stackcs cs = { -1 };
    int len = 0;

    //对表达式进行遍历
    for (int i = 0; expression[i]; i++) {
        char ch = expression[i];
        //如果是数字
        if (isdigit(ch)) {
            //放入后缀表达式
            postfix[len++] = ch;
            postfix[len++] = ' ';
            continue;
        }

        //如果不是数字 那就是操作符
        int pri = getPriority(ch);

        //只要是正常的操作符
        if (pri != -1) {
            //栈为空
            if (isEmpty(&cs)) {
                //操作符入栈
                pushcs(&cs, ch);
            }
            //栈不为空
            else {
                //如果是右括号
                if (ch == ')') {
                    //直至栈空之前
                    while (!isEmpty(&cs)) {
                        //找到左括号

                        //弹出一个操作符
                        char top = topcs(&cs);
                        popcs(&cs);
                        if (top != '(') {
                            //如果不是左操作符
                            //就进入postfix数组
                            postfix[len++] = top;
                            postfix[len++] = ' ';
                        }
                        //如果是左括号
                        //循环结束 就是将左右括号之间的操作符放入
                        else {
                            break;
                        }
                    }
                }
                //如果不是右括号
                else {
                    //栈不为空 并且栈顶元素不是左括号
                    while (!isEmpty(&cs) && topcs(&cs) != '(') {
                        //不是括号的操作符
                        //看一下栈顶元素
                        char top = topcs(&cs);

                        //将栈顶元素的优先级和目前拿到手里的操作符的优先级比较
                        //当前操作符优先级小于栈顶元素
                        if (pri <= getPriority(top)) {
                            //该操作符就不放入操作符栈里面
                            //而是直接输出
                            postfix[len++] = top;
                            postfix[len++] = ' ';

                            //并且要弹出栈顶元素
                            //直至遇到优先级更低的元素
                            popcs(&cs);
                        }
                        else{
                            break;
                        }
                    }
                    //如果都没有 就将该操作符入栈
                    pushcs(&cs, ch);
                }
            }
        }
    }

    //表达式已经遍历完了
    //现在将操作符栈里面的所有操作符弹出即可
    while (!isEmpty(&cs) && topcs(&cs) != '(') {
        char top = topcs(&cs);
        postfix[len++] = top;
        postfix[len++] = ' ';
        popcs(&cs);
    }
    postfix[len] = '�'; // 添加字符串结束符
}

//计算后缀表达式的值
double evaluate(char postFix[])
{
    Stackns ns = { -1 };
    for (int i = 0; postFix[i]; i++)
    {
        char ch = postFix[i];
        //如果是数字
        if (isdigit(ch)) {
            //放入数字栈里面
            pushns(&ns, ch - '0');
            continue;
        }
        //如果该字符不是空格
        //则该字符是操作符
        if (ch != ' ') {
            //弹出来两个元素进行运算
            double right = topns(&ns);
            popns(&ns);
            //先弹出来的位于表达式的右侧
            //后弹出来的位于表达式的左侧
            double left = topns(&ns);
            popns(&ns);

            //下面开始运算
            //运算完之后结果直接入栈
            double result = 0.0;
            switch (ch) {
            case '+':
                result = left + right;
                break;
            case '-':
                result = left - right;
                break;
            case '*':
                result = left * right;
                break;
            case '/':
                result = left / right;
                break;
            }
            pushns(&ns, result);
        }
    }

    //返回最后的一个数字
    return topns(&ns);
}

int main()
{
    char expression[1024] = { 0 };
    char postfix[1024] = { 0 };

    //输入expression表达式
    printf('请输入中缀表达式：');
    scanf('%[^
]%*c', expression);

    //中缀变后缀
    toPostfix(expression, postfix);

    //打印后缀表达式
    printf('后缀表达式：%s\n', postfix);

    //限定结果为两位小数
    printf('计算结果：%.2lf\n', evaluate(postfix));

    system('pause');
    return 0;
}

代码解释：

数据结构定义: 定义了两个栈 Stackcs 和 Stackns 分别存储字符和数字，使用数组和栈顶指针实现。
栈操作函数: 实现了栈的常见操作：isEmpty 判断栈是否为空, topcs 获取字母栈顶元素, topns 获取数字栈顶元素, pushcs 入字母栈, pushns 入数字栈, popcs 出字母栈, popns 出数字栈。
优先级函数 getPriority: 根据操作符返回优先级，方便比较运算符优先级。
中缀转后缀函数 toPostfix: 遍历中缀表达式，根据操作符和括号的优先级进行入栈和出栈操作，最终生成后缀表达式。
后缀表达式求值函数 evaluate: 遍历后缀表达式，遇到数字则入栈，遇到操作符则弹出两个数字进行运算并将结果入栈，最终栈顶元素即为表达式的值。
主函数 main: 读取用户输入的中缀表达式，调用 toPostfix 函数将其转换为后缀表达式并打印，然后调用 evaluate 函数计算表达式的值并打印。

示例：

输入：1+2*(3-1)

输出：

后缀表达式：1 2 3 1 - * + 计算结果：5.00