能够把中缀表达式转换成后缀表达式,是在为http://www.rqnoj.cn/Problem_18.html 这一题做准备,感觉写的还不错,关键是在优先级的处理方面(compare函数),整个代码如下(包含驱动函数main):
只支持+-*^()和变量
#include <stdio.h>
#include <ctype.h>
#define MAX 101
#define NUM 0
#define CHAR 1
#define OPER 2
#define STR +-*^()
const unsigned used = 100000000;
#define bits 8
struct t{
unsigned num[MAX];
char type[MAX];
int len;
}std;
unsigned stack[50];
int top;
#define push(a) ({stack[top++] = a;})
#define pop() ({stack[--top];})
void add(struct t *to, unsigned key, char type)
{
to->num[to->len] = key;
to->type[to->len] = type;
to->len++;
}
int par[6][6] ={{-1, -1, 1, 1, 1, -1},
{-1, -1, 1, 1, 1, -1},
{-1, -1, -1, 1, 1, -1},
{-1, -1, -1, -1, 1, -1},
{1, 1, 1, 1, 1, 0},
{-1, -1, -1, -1, 0, 1},};
/*
0:加法
1:减法
2:乘法
3:求幂
4:正括号
5:反括号
*/
int compare(int a, int b)
{
char *i, *j;
i = strchr(STR, a);
j = strchr(STR, b);
a = i - STR;
b = j - STR;
return par[a][b];
}
void change(struct t *to, char *from)
{
int i, j;
int ch;
unsigned t;
push(\'(\');
for(i = 0; from[i] != \'\\0\'; i++){
ch = from[i];
if(strchr(STR, ch) != NULL){ /* 处理三种情况 */
j = compare(stack[top - 1], ch);
while(j < 0){
add(to, pop(), CHAR);
j = compare(stack[top - 1], ch);
}
if(j == 0){
pop();
}else{
push(ch);
}
}else if(isdigit(ch)){
t = 0;
while(isdigit(from[i])){
t *= 10;
t += from[i++] - \'0\';
}
i--;
add(to, t, NUM);
}else if(ch == \'a\'){
add(to, ch, OPER);
}
}
while(top != 1){ /* 把最后几个符号去掉, 但是在函数
开始加入的正括号不加入 */
add(to, pop(), CHAR);
}
}
int main(void)
{
int i;
char tmp[51];
scanf(%s, tmp);
change(&std, tmp);
for(i = 0; i < std.len; i++){
if(i != 0){
printf( );
}
switch(std.type[i]){
case NUM:
printf(%u, std.num[i]);
break;
case CHAR:
printf(%c, std.num[i]);
break;
case OPER:
printf(%c, std.num[i]);
break;
}
}
printf(\\n);
return 0;
}