编译原理【c语言实现】将四则运算中缀表达式（带括号，有空格，有变量）化为后缀表达式

本文主要是介绍编译原理【c语言实现】将四则运算中缀表达式（带括号，有空格，有变量）化为后缀表达式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

示范1

输入中缀

var+2 +33

输出后缀

var 2 + 33 +

示范2

中缀

((1+3)*2 + 5)*33

后缀

1 3 + 2 * 5 + 33 *

思路

等以后有时间我会完善。整体受到编译原理教材的启示。关键就是写出左递归的产生式，然后消除左递归，表示成容易用程序实现的方式。

代码

/*  左递归expr -> expr + term  		{print(‘+’)}        | expr - term    		{print(‘-’)}| termterm -> term * factor 		{print(‘*’)}        |  term / factor 		{print(‘/’)}        |  factorfactor -> (expr)|  id				{ print(lexeme) }        |  num				{ print(tokenval) }
-----------------------------------------------------消除左递归后expr -> term restrest -> + term 	print{('+')} 	rest| - term 	print{('-')} 	rest| 空term   -> factor rest2rest2  -> * factor 	print{('*')} rest2| / factor 	print{('/')} rest2| 空factor -> (expr)| id            	{print(id)}| num           	{print(num)
*/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>using namespace std;#define TKN_NUM  500
#define TKN_ID   600int LookAhead; //词法单元类型
char lexeme[1000];//词素
int tokenval = 0; //记录完整的数值
int getToken();
void Match(int i);
void factor();
void rest2();
void term();
void rest();
void expr();int getToken(){int i, t;while(1){t = getchar();if(t == ' ' || t == '\t');else if(isdigit(t)){tokenval = 0;do {tokenval = tokenval * 10 + t -'0';t = getchar();} while (isdigit(t));ungetc(t, stdin); //把字符 char（一个无符号字符）推入到指定的流 stream 中，以便它是下一个被读取到的字符。即回退return TKN_NUM;}else if(isalpha(t)){i = 0;do {lexeme[i++]=t;t = getchar(); }while( isalpha(t) || isdigit(t) );lexeme[i]='\0'; ungetc(t, stdin);//回退return TKN_ID;}else{tokenval = 0;return t; //+ - * / ( ).etc}}
}
void Match(int i){if(i == LookAhead){LookAhead = getToken();}else{printf("\nmatch error\n", i);exit(1);}
}
void factor(){if( LookAhead==TKN_NUM) {printf("%d ",tokenval); Match(LookAhead); }else if( LookAhead==TKN_ID) {printf("%s ",lexeme); Match(LookAhead);}else if( LookAhead == '('){//stack_.push_back('(');LookAhead = getToken();expr();if(LookAhead != ')'){printf("\nBracket mismatch\n" );exit(1); //结束程序}LookAhead = getToken();}else{printf("\nerror\n" );exit(1); //结束程序}
}
void rest2(){switch( LookAhead ) {case '*':Match('*'); factor(); printf("* "); rest2(); // rest --> + term {print('+')} restbreak;case '/':Match('/'); factor(); printf("/ "); rest2(); // rest --> - term {print('-')} restbreak;default:   // rest --> 空break;}
}
void term(){factor();rest2();
}
void rest(){switch(LookAhead){case '+':Match('+'); term(); printf("+ "); rest();break;case '-':Match('-'); term(); printf("- ");rest();default: break;}
}
void expr(){term();rest();
}
int main(){printf("Input inOrder expression:\n");LookAhead = getToken();printf("postOrder is:\n");expr();return 0;
}