刚刚做完中缀表达式转前缀表达式，想着试试看能不能把中缀表达式转化为前缀表达式，我自己笨想不来怎么做，然后就在网上找了很多教程，看看原理以及思路。
找了一个最笨的解决方法就是先逆序读中缀表达式，然后照着上一次用中缀转后缀的方法，得到由逆序的中缀表达式转化为的后缀表达式，再将这个后缀表达式逆序输出来。
具体实现代码如下： #include <stdio.h>#include <stdlib.h>#include <math.h>#include <ctype.h>typedef struct{ char *top; char *base; int size;}sqStack;void initStack(sqStack *s){ s->base = (char *)malloc(100 *sizeof(char)); if(!s->base){ exit(0); } s->top = s->base; s->size = 100;}int StackLen(sqStack s){ return (s.top - s.base); //指针地址相减是算两个地址之间隔了几个元素， 指针地址不能相加}void Push(sqStack *s, char e){ if(s->top - s->base >= s->size){ s->base = (char *)realloc(s->base, (s->size + 10)*sizeof(char)); if(!s->base){ exit(0); } s->top = s->base + s->size; s->size = s->size + 10; } *(s->top) = e; s->top ++;}void Pop(sqStack *s, char *e){ if(s->top == s->base){ return; } s->top --; *e = *(s->top); // s->top --;}int main(){ printf("请输入列表：n"); sqStack s, q, l; initStack(&s); //存储输入的中缀表达式 initStack(&q); //存储运算符号 initStack(&l); //存储得到后缀表达式 int n, sum = 0,i = 0; char str[10]; char x; char a, b; scanf("%c", &x); while('#' != x){ Push(&s, x); scanf("%c", &x); //将输入的中缀表达式存入栈中 } int len = StackLen(s); printf("len:%dn", len); for(int i=0;i<len;i++){ //根据栈的先进后出的规则倒序输出 Pop(&s, &a); printf("a:%cn", a); if(isdigit(a)){ // 计算后缀表达式 Push(&l, a); } else { if (')' == a) { Push(&q, a); } else if ('(' == a) { Pop(&q, &b); while (')' != b) { Push(&l, b); Pop(&q, &b); } } else if ('+' == a || '-' == a) { if (!StackLen(q)) { Push(&q, a); } else { do { Pop(&q, &b); if (')' == b) { Push(&q, b); } else { Push(&l, b); } } while (b != ')' && StackLen(q)); Push(&q, a); } } else if (a == '*' || a == '/' || a == '(') { Push(&q, a); } } } while (StackLen(q)){ Pop(&q, &b); Push(&l, b); } while (StackLen(l)){ //逆序赎回后缀表达式 Pop(&l, &a); printf("%c ", a); }}
其实感觉用数组来存储数据会简单很多，但是上一次代码是用结构体加指针存的，就懒得再改了，能的出结果就行了，粗浅的测试了一下没什么问题，生动的心锁刚开始学算法，有什么问题还请大佬多多指教。