当前位置： 首页 > article >正文

中缀表达式转后缀表达式

article 2024/11/17 11:47:57

完整代码：

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6013)
#pragma warning(disable:4013)

#include<stdio.h>
#define MAXSIZE 100

/*
算术中缀表达式转后缀表达式
输入：9+(3-1)*3+10/2
输出：9 3 1 － 3 * + 10 2 / +

原理：
数字直接输出，
如果是右括号或者输入的优先级不大于（小于或等于）栈顶符号，
则输出栈顶元素（这个判断发生时）
然后再与下一个栈顶元素判断；
判断完之后在进行入栈操作。
*/

// 栈部分
typedef char SElemType;
typedef int Status;
typedef struct {
	SElemType data[MAXSIZE];
	int top;
} SqTack;

void InitStack(SqTack* S) {
	S->top = -1;
	for (int i = 0; i < MAXSIZE; i++) {
		S->data[i] = 0;
	}
}

Status GetTop(SqTack S, SElemType* e) {
	if (S.top == -1) {
		return 1;
	}
	*e = S.data[S.top];
	return 0;
}

Status Push(SqTack* S, SElemType e) {
	if (S->top == MAXSIZE - 1) {
		return 0;
	}
	S->top++;
	S->data[S->top] = e;
	return 1;
}

Status Pop(SqTack* S, SElemType* e) {
	if (S->top == -1) {
		return 0;
	}
	*e = S->data[S->top];
	S->top--;
	return 1;
}

void cpu(SqTack* S, char ch) {
	int flag;
	char tope, e;

	do {
		if (GetTop(*S, &tope)) {
			Push(S, ch);    // 入栈；
			break;
		}
		flag = cpu1(ch, tope);
		if (flag == 1) {
			Pop(S, &e); //出栈；
			printf("%c ", e);
		}
		else if (flag == 0) {
			Push(S, ch);    // 入栈；
		}
		else if (flag == -1) {
			while (1) {
				Pop(S, &e);
				if (e == '(') { break; }
				else { printf("%c ", e); }
			}
			flag = 0;
		}
	} while (flag);
}

// 逻辑处理函数，返回0，当前元素入栈；返回1，栈顶元素出栈（还需要继续比较）
// 返回-1，涉及括号的逻辑处理
Status cpu1(char ch, char tope) {
	// 利用ASCII码表来判断
	// (:40   ):41    *:42   +:43   -:45   /:47
	// * = / > + = -
	// (直接返回1，)输出到(，（后缀表达式不要求输出括号）
	switch (ch) {
	case 40:
		return 0;
	case 41:
		return -1;
	case 42:	// *
		if (tope == 42 || tope == 47) {
			return 1;
		}
		else {
			return 0;
		}
	case 47:	// /
		if (tope == 42 || tope == 47) {
			return 1;
		}
		else {
			return 0;
		}
	case 43:	// +
		if (tope == 43 || tope == 45 || tope == 42 || tope == 47) {
			return 1;
		}
		else {
			return 0;
		}
	case 45:	// -
		if (tope == 43 || tope == 45 || tope == 42 || tope == 47) {
			return 1;
		}
		else {
			return 0;
		}
	default:
		return 404;
	}
}

// 转换函数
void convert() {
	//    char s[MAXSIZE]={0};
	SqTack S;
	InitStack(&S);

	char ch, e;
	int i, flag, intt;

	i = 0;
	// 考虑第一个字符是（的情况
	ch = getchar();	// 查看下一个字符
	if (ch < '0' || ch> '9') {
		i = 1;
	}
	ungetc(ch, stdin);	// 回退字符

	while (1) {
		if (i % 2 == 0) {
			scanf("%d", &intt);
			printf("%d ", intt);
		}
		else {
			ch = getchar();
			if (ch == '\n') {    //终止
				while (S.top != -1) { //输出栈中剩余的元素
					Pop(&S, &e);
					printf("%c ", e);
				}
				break;
			}
			else {    // 处理其他符号之间的逻辑
				if (S.data[S.top] == '(') {
					Push(&S, ch);    // 入栈
				}
				else if (S.top != -1) {    // 栈非空
					cpu(&S, ch);
				}
				else {
					Push(&S, ch);    // 入栈
				}
			}
			ch = getchar();	// 查看下一个字符
			if (ch < '0' || ch> '9') {
				i--;
			}
			ungetc(ch, stdin);	// 回退字符
		}
		i++;
	}
}

int main() {
	while (1) {
		convert();
		printf("\n");
	}
	return 0;
}

一、基本原理

中缀表达式是我们常见的数学表达式形式，运算符位于操作数之间，如9+(3 - 1)*3+10/2。后缀表达式则将运算符紧跟在其操作数之后，上述中缀表达式对应的后缀表达式是9 3 1 - 3 * + 10 2 / +。

转换原理基于以下规则：

  • 数字直接输出。因为数字在后缀表达式中的顺序与中缀表达式中相同。
  • 对于运算符和括号，依据它们的优先级以及栈的当前状态来处理。当遇到右括号或者输入的运算符优先级不高于（小于或等于）栈顶运算符优先级时，输出栈顶元素，然后继续与新的栈顶元素比较，完成比较后再进行入栈操作，以此保证后缀表达式符合运算顺序。

二、栈相关功能函数解释

（一）InitStack函数

void InitStack(SqTack* S) {
    S->top = -1;
    for (int i = 0; i < MAXSIZE; i++) {
        S->data[i] = 0;
    }
}

此函数用于初始化栈。将栈顶指针top设为 - 1，表明栈为空。同时把栈的存储数组data的所有元素初始化为 0，为存储元素做准备。

（二）GetTop函数

Status GetTop(SqTack S, SElemType* e) {
    if (S.top == -1) {
        return 1;
    }
    *e = S.data[S.top];
    return 0;
}

其作用是获取栈顶元素。若栈为空（top为 - 1），返回 1，表示获取失败；若栈非空，将栈顶元素值赋给e指向的变量，并返回 0，表示获取成功。

（三）Push函数

Status Push(SqTack* S, SElemType e) {
    if (S->top == MAXSIZE - 1) {
        return 0;
    }
    S->top++;
    S->data[S->top] = e;
    return 1;
}

该函数用于将元素e入栈。首先检查栈是否已满（top是否等于MAXSIZE - 1），若已满，返回 0（入栈失败）；若有空间，top加 1，并将e存入data[top]，返回 1（入栈成功）。

（四）Pop函数

Status Pop(SqTack* S, SElemType* e) {
    if (S->top == -1) {
        return 0;
    }
    *e = S->data[S->top];
    S->top--;
    return 1;
}

此函数实现栈顶元素出栈。先检查栈是否为空（top为 - 1），为空则返回 0（出栈失败）；非空时，将栈顶元素值赋给e指向的变量，top减 1，返回 1（出栈成功）。

三、convert函数详细解释

void convert() {
    SqTack S;
    InitStack(&S);

    char ch, e;
    int i = 0, flag, intt;

    ch = getchar();  // 查看下一个字符
    if (ch < '0' || ch > '9') {
        i = 1;
    }
    ungetc(ch, stdin);  // 回退字符

    while (1) {
        if (i % 2 == 0) {
            scanf("%d", &intt);
            printf("%d ", intt);
        } else {
            ch = getchar();
            if (ch == '\n') {  // 终止
                while (S.top!= -1) {  // 输出栈中剩余的元素
                    Pop(&S, &e);
                    printf("%c ", e);
                }
                break;
            } else {  // 处理其他符号之间的逻辑
                if (S.data[S.top] == '(') {
                    Push(&S, ch);  // 入栈
                } else if (S.top!= -1) {  // 栈非空
                    cpu(&S, ch);
                } else {
                    Push(&S, ch);  // 入栈
                }
            }
            ch = getchar();  // 查看下一个字符
            if (ch < '0' || ch > '9') {
                i--;
            }
            ungetc(ch, stdin);  // 回退字符
        }
        i++;
    }
}
  • 整体流程：
    • 首先初始化一个栈S。然后读取输入字符来判断第一个字符的类型，如果不是数字（0 - 9），则将标志i设为 1。这里通过ungetc回退字符，以便后续正确处理。
    • 接着进入一个无限循环。根据i的值来处理输入，如果i是偶数，说明期望输入数字，使用scanf读取并输出。如果i是奇数，说明期望输入运算符或括号，读取字符ch。
    • 当ch是换行符\n时，表示中缀表达式输入结束，此时将栈中剩余元素依次弹出并输出。如果ch不是换行符，根据栈的状态处理：若栈顶是(，直接将ch入栈；若栈非空，调用cpu函数处理；若栈为空，也将ch入栈。每次处理完一个字符后，再查看下一个字符，若不是数字则调整i的值，并回退字符。
  • 作用总结：此函数是中缀表达式转后缀表达式的核心控制逻辑，通过循环处理输入字符，协调数字输出、栈操作和符号处理，最终实现完整的转换。

四、逻辑处理函数详细解释

（一）cpu函数

void cpu(SqTack* S, char ch) {
    int flag;
    char tope, e;

    do {
        if (GetTop(*S, &tope)) {
            Push(S, ch);    // 入栈；
            break;
        }
        flag = cpu1(ch, tope);
        if (flag == 1) {
            Pop(S, &e); //出栈；
            printf("%c ", e);
        }
        else if (flag == 0) {
            Push(S, ch);    // 入栈；
        }
        else if (flag == -1) {
            while (1) {
                Pop(S, &e);
                if (e == '(') { break; }
                else { printf("%c ", e); }
            }
            flag = 0;
        }
    } while (flag);
}
  • 逻辑流程：
    • 首先尝试获取栈顶元素。若栈为空（GetTop返回非零值），则将当前字符ch入栈并结束函数。
    • 若栈不为空，调用cpu1函数，根据cpu1函数的返回值flag来处理。
    • 当flag == 1时，说明当前字符ch的优先级小于等于栈顶元素的优先级，需要将栈顶元素弹出并输出，然后继续循环判断新的栈顶元素。
    • 当flag == 0时，将当前字符ch入栈。
    • 当flag == - 1时，表示遇到了右括号)，此时需要不断弹出栈顶元素并输出，直到遇到左括号(。完成后将flag设为 0，继续循环（可能还有其他操作需要处理）。
  • 作用总结：该函数是处理单个运算符或括号与栈交互的关键逻辑，根据当前字符和栈顶元素的关系，决定是入栈、出栈还是处理括号相关的特殊情况。

（二）cpu1函数

Status cpu1(char ch, char tope) {
    // 利用ASCII码表来判断
    // (:40   ):41    *:42   +:43   -:45   /:47
    // * = / > + = -
    // (直接返回1，)输出到(，（后缀表达式不要求输出括号）
    switch (ch) {
    case 40:
        return 0;
    case 41:
        return -1;
    case 42:    // *
        if (tope == 42 || tope == 47) {
            return 1;
        }
        else {
            return 0;
        }
    case 47:    // /
        if (tope == 42 || tope == 47) {
            return 1;
        }
        else {
            return 0;
        }
    case 43:    // +
        if (tope == 43 || tope == 45 || tope == 42 || tope == 47) {
            return 1;
        }
        else {
            return 0;
        }
    case 45:    // -
        if (tope == 43 || tope == 45 || tope == 42 || tope == 47) {
            return 1;
        }
        else {
            return 0;
        }
    default:
        return 404;
    }
}
  • 逻辑流程：
    • 根据当前字符ch的值进行switch判断。
    • 如果ch是左括号(，返回 0，表示此括号应入栈。
    • 如果ch是右括号)，返回 - 1，表示需要处理括号内元素的输出。
    • 对于运算符：
      • 如果ch是*或/，且栈顶元素也是*或/，返回 1，表示当前运算符优先级小于等于栈顶运算符，应先输出栈顶运算符；否则返回 0，表示可入栈。
      • 如果ch是+或-，且栈顶元素是+、-、*或/，返回 1；否则返回 0。
    • 如果ch是其他值（这里返回 404，错误标识）。
  • 作用总结：此函数是整个转换逻辑中的关键判断部分，通过比较当前字符和栈顶字符，依据运算符优先级和括号情况，决定cpu函数的操作。

http://www.kler.cn/a/397208.html

相关文章：

  • 信息收集—JS框架识别泄露提取API接口泄露FUZZ爬虫插件项目
  • 智能化护士排班系统的设计与实现（文末附源码）
  • 软件设计师 - 第1章 计算机网络概论
  • CSS Module：告别类名冲突，拥抱模块化样式（5）
  • 【数据结构】线性表——栈与队列
  • 跟我学C++中级篇——Design Patterns的通俗说法
  • 重学SpringBoot3-各种配置的优先级对比
  • [JAVA]MyBatis框架—如何获取SqlSession对象实现数据交互（基础篇）
  • 使用 ts-node 运行 ts文件，启动 nodejs项目
  • 八、鸿蒙开发-网络请求、应用级状态管理
  • 去地面算法——depth_clustering算法调试（1）
  • 视频孪生技术在金融银行网点场景中的应用价值
  • 使用json配置动态区间及动态执行公式
  • IOPaint模型部署教程
  • 【图像压缩感知】论文阅读：Content-Aware Scalable Deep Compressed Sensing
  • Oracle EBS FORM界面获取某LOV的方法
  • CentOS 源码安装FFmpeg
  • 【Qt】报错error: undefined reference to `vtable for的最简单解决
  • 企业选择CPU服务器都有哪些用途？
  • 内部排序和外部排序以及常见算法和时间复杂度
  • C# VS的常用功能(一) 视图篇
  • 小地图（二）
  • yaml的学习记录
  • 我们是如何实现 TiDB Cloud Serverless 的 - 成本篇
  • Java爬虫（HttpURLConnection）详解
  • 分布式----Ceph部署