算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。
输入格式:
输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。
输出格式:
在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。
样例">输入样例:
2+3*(7-4)+8/4
输出样例:
2 3 7 4 - * + 8 4 / +
代码：（我自己认为比较好理解的一种）
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Stack {
char c[20];
int top;
};
Stack* creatStack() {
Stack* newStack = (Stack*)malloc(sizeof(struct Stack));
newStack->top = -1;
return newStack;
}
void push(Stack* stack, char c) {
stack->top++;
stack->c[stack->top] = c;
}
char pop(Stack* stack) {
return stack->c[stack->top--];
}
int main() {
Stack* newStack = creatStack();
char ch1[150];
ch1['('] = 0;
ch1['+'] = 1;
ch1['-'] = 1;
ch1['*'] = 2;
ch1['/'] = 2;
char s[21];
scanf("%s", s);
int length = strlen(s);
int flag = 0;
for (int i = 0; i < length; i++) {
if (s[i] == '(') {
push(newStack, s[i]);
}
else if (s[i] == ')') {
char t;
t = pop(newStack);
while (t != '(') {
printf(" %c", t);
t = pop(newStack);
}
flag = 1;
}
else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
if (s[i] == '+' && (s[i-1] == '(' || i==0));
else if (s[i] == '-' && (s[i-1] == '(' || i==0)) {
printf("-");
}
else if (ch1[s[i]] > ch1[newStack->c[newStack->top]] || newStack->top == -1) {
push(newStack, s[i]);
flag = 1;
}
else {
printf(" %c", pop(newStack));
while (ch1[s[i]] <= ch1[newStack->c[newStack->top]] && newStack->top != -1) {
printf(" %c", pop(newStack));
}
push(newStack, s[i]);
flag = 1;
}
}
else {
if (flag)
{
printf(" ");
flag = 0;
}
printf("%c", s[i]);
}
}
while (newStack->top != -1) {
printf(" %c", pop(newStack));
}
return 0;
}注意点：
1.在创建顺序表的时候，数组是char类型的（我曾经定义成int型）
typedef struct Stack {
char c[20];
int top;
};2.push函数与pop函数在操作top的先后顺序不同
push函数是先将top++，再用top的值
void push(Stack* stack, char c) {
stack->top++;
stack->c[stack->top] = c;
}而pop函数是先用top的值，再--
所以不能写成push函数那样
//错误
char pop(Stack* stack) {
stack->top--;
return stack->c[stack->top];
}//正确
char pop(Stack* stack) {
return stack->c[stack->top--];
}3.定义的ch1数组是为了之后比较优先级，*，/ 的优先级最高，+，- 次之，（ 最低
char ch1[150];
ch1['('] = 0;
ch1['+'] = 1;
ch1['-'] = 1;
ch1['*'] = 2;
ch1['/'] = 2;
4.解决问题的主体是一个大的多分支选择结构，就是判断当前字符是什么，然后进行相应的操作
遇见（ 直接入栈
if (s[i] == '(') {
push(newStack, s[i]);
}遇见 ） 就要对栈中的运算符进行输出了
else if (s[i] == ')') {
char t;
t = pop(newStack);
while (t != '(') {
printf(" %c", t); //这里的%c前面有空格
t = pop(newStack);
}
flag = 1;
}遇见 +，-，*，/ 的情况：
else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
if (s[i] == '+' && (s[i-1] == '(' || i==0));
else if (s[i] == '-' && (s[i-1] == '(' || i==0)) {
printf("-");
}
else if (ch1[s[i]] > ch1[newStack->c[newStack->top]] || newStack->top == -1) {
push(newStack, s[i]);
flag = 1;
}
else {
printf(" %c", pop(newStack)); //这里的%c前面有空格
while (ch1[s[i]] <= ch1[newStack->c[newStack->top]] && newStack->top != -1{
printf(" %c", pop(newStack)); //这里的%c前面有空格
}
push(newStack, s[i]);
flag = 1;
}
}下面这段代码是处理负数的情况，比如 -7，它前面的负号我们不能当成运算符来看，而+7前的正号我们不用操作
一个算式出现负数有两种情况：给负数加括号与不加括号
当负数是第一个数或者负数是（ 后第一个数时，不加括号，例如 -5 + 3*（-6 +8）
其他情况便是负数在算式中的情况，例如：8+（-9）*6
显然这段代码是处理负数是第一个数或者负数是（ 后第一个数时的情况
if (s[i] == '+' && (s[i-1] == '(' || i==0));
else if (s[i] == '-' && (s[i-1] == '(' || i==0)) {
printf("-");
}然后是处理运算符优先级的问题：
else if (ch1[s[i]] > ch1[newStack->c[newStack->top]] || newStack->top == -1) {
push(newStack, s[i]);
flag = 1;
}
else {
printf(" %c", pop(newStack)); //这里的%c前面有空格
while (ch1[s[i]] <= ch1[newStack->c[newStack->top]] && newStack->top != -1){
printf(" %c", pop(newStack)); //这里的%c前面有空格
}
push(newStack, s[i]);
flag = 1;
}要入栈的运算符比栈顶的运算符优先级高，直接入栈。
要入栈的运算符比栈顶的运算符优先级低或相等，将栈顶元素出栈并输出，然后继续判断，直到栈为空或者要入栈的运算符比栈顶的运算符优先级高，然后入栈。
然后是处理数字（直接输出）：
else {
if (flag)
{
printf(" ");
flag = 0;
}
printf("%c", s[i]);
}注意这个else不是判断 +，-，*，/ 分支中的else！
最后将栈中剩下的运算符输出即可：
while (newStack->top != -1) {
printf(" %c", pop(newStack)); //这里的%c前面有空格
}5.flag什么时候改变的问题：
输出运算符的时候输出空格和运算符，然后将flag置1