题目描述
就是把我们平常写的运算表达式换成另外一种表达式,运算符前面两个数字执行相关操作。用图说明一下:
比如3+2 -> 3 2 +
比如3 + 3 * 2 -> 3 3 2 * +
再比如 3 + (3 * 2 + 2) * 3 ->3 3 2 * 2 + 3 * +
程序设计思路
特殊情况:在中间如果遇到(左括号,除非遇到)右括号,否则不弹出,符号依旧入栈处理,然后在遇到)右括号之前的符号,按照上面规矩出入栈并输出,直到遇到左括号截止出栈。当遇到右括号,从栈顶一直到左括号的内容全部依次出栈并输出,左括号出栈不输出。当表达式遍历结束,依次出栈并输出
备注:也就是说当 ( 左括号做栈顶的时候,当成优先级低处理
写栈之括号匹配问题的时候,用的顺序栈处理,这次用链式栈处理
还是老规矩,先把栈做成一个动态库
代码设计
话不多说,直接上代码:
main.c
#include <stdio.h>
#include <stdlib.h>
#include "linkstack.h"
int main()
{
char str_expre[100] = { '\0' };//输入
char res_expre[100] = { '\0' };//输出
//创建栈
link_stack *stack = create_stack();
while(scanf("%s",str_expre) != EOF && stack != NULL) {
int index = 0;
int cursor = 0;//结果游标
while(str_expre[index] != '\0') {
//这里给一个while循环,实现一个数字的拼接,数字单独处理
if(str_expre[index] >= 0 && str_expre[index] <= '9') {
//如果是数字内部直接循环赋值到另外一个数组中去
while(1) {
if(str_expre[index] < '0' || str_expre[index] > '9') {
break;
}
res_expre[cursor++] = str_expre[index++];
}
//最后赋值过去给数字之间一个空格
res_expre[cursor++] = ' ';
}
if(is_empty(stack)) {
push_stack(stack,(int)str_expre[index]);
} else if(!is_empty(stack) && str_expre[index] != '\0') {
char top_elem = (char)top_stack(stack);
if(top_elem == '(') {
//这种情况直接进栈
push_stack(stack,(int)str_expre[index]);
} else if(top_elem == '*' && (str_expre[index] == '+' || str_expre[index] == '-')) {
//这种情况直接依次出栈并且出栈元素不等于(
while(top_elem != '('){
res_expre[cursor++] = top_elem;
res_expre[cursor++] = ' ';
pop_stack(stack);
top_elem = (char)top_stack(stack);
}
//出完栈之后,把当前符号入栈
push_stack(stack,(int)str_expre[index]);
} else if((top_elem == '+' || top_elem == '-') && str_expre[index] != ')') {
//栈顶优先级低,还是直接入栈
push_stack(stack,(int)str_expre[index]);
} else if(str_expre[index] == ')') {
//一直到(,必须要连续出栈,
while(top_elem != '(') {
//连续出栈
res_expre[cursor++] = top_elem;
res_expre[cursor++] = ' ';//给数字之间一个空格
pop_stack(stack);
top_elem = (char)top_stack(stack);
}
//‘(’记得出栈
pop_stack(stack);
}
}
index++;
}
//整体循环完毕,把栈里面内容直接输出
while(!is_empty(stack)) {
res_expre[cursor++] = (char)top_stack(stack);
res_expre[cursor++] = ' ';
pop_stack(stack);
}
printf("%s\n",res_expre);
}
return 0;
}
编译并查看运行结果:
利用库里面的顺序栈的操作代码
#include <cstdio>
#include <cstdlib>
extern "C" {
#include <seqstack1.0.h>
}
int main()
{
t_seq_stack* p_head = create_stack();
char str[100] = {'\0'};
char res[100] = {'\0'};
while(scanf("%s",str) != EOF && p_head != NULL) {
//遍历整个中缀表达式字符串
int index = 0;
int cursor = 0;
while(str[index] != '\0') {
//判断是否是数字
//方便进行拼接
if(str[index] >= '0' && str[index] <= '9') {
while(1) {
//什么时候跳出
if(str[index] < '0' || str[index] > '9') {
break;
}
res[cursor++] = str[index++];
}
//拼接完了之后给一个空格
res[cursor++] = ' ';
}
//下面开始放入其他符号
//这里就走的是不是数字嘛
if(is_empty(p_head)) {
//空栈是直接入栈
//这里面是一个void*类型的指针
push_stack(p_head,&str[index]);
}else if(!is_empty(p_head) && str[index] != '\0') {
//拿到栈顶元素进行比较
char *top_elem = (char*) top_stack(p_head);
//如果是左括号直接进栈
if(str[index] == '(') {
push_stack(p_head,&str[index]);
} else if(*top_elem == '*' && (str[index] == '+' || str[index] == '-')) {
//栈顶优先级高,依次出栈
//但是出栈元素不等于(
while(*top_elem != '(') {
//这里出栈其实就是插入到res数组里面
res[cursor++] = *top_elem;
//中间给一个空格
res[cursor++] = ' ';
pop_stack(p_head);
top_elem = (char*)top_stack(p_head);
}
//出完栈之后,还要把当前元素入栈
push_stack(p_head,&str[index]);
//栈顶优先级低的情况,直接入栈
} else if((*top_elem == '+' || *top_elem == '-') || str[index] == '*') {
//栈顶优先级低,还是直接入栈
push_stack(p_head,&str[index]);
} else if(str[index] == ')') {
//连续出栈,直到匹配到左括号
while(*top_elem != '(') {
res[cursor++] = *top_elem;
res[cursor++] = ' ';
pop_stack(p_head);
top_elem = (char*)top_stack(p_head);
}
//把左括号给出栈
pop_stack(p_head);
}
}
index++;
}
//整体遍历
while(!is_empty(p_head)) {
char *top_elem = (char*)top_stack(p_head);
//上面循环完之后,把栈里面剩余的内容继续输出
res[cursor++] = *top_elem;
res[cursor++] = ' ';
pop_stack(p_head);
}
printf("%s\n",res);
}
return 0;
}