跳至正文

中缀表达式转换后缀表达式

  • 技术

能够把中缀表达式转换成后缀表达式,是在为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;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注