逆波兰表达式(Reverse Polish Notation)又叫后缀表达式。它是一种非常的表达式，可以将复杂的表达式转换成可以依靠简单的操作得到结果的表达。下面这段C语言即是用于实现将中缀表达式转换成后缀表达式，并计算出结果。相比于网上现有的程序此程序的最大优点在于：1、支持浮点运算；2、支持以符号和单词代表数值；3、支持参与运算的是多位数；
中缀转换后缀的规则：
1、依次读取中缀表达式，如果遇到操作数(即数字或代表数字的字母组合)，直接将其输出为后缀表达式的一部分；
2、如果读取到操作符，则将其放入到一个栈中，遇到左括号时我们也将其放入栈中；
3、上述操作符入栈前先需比较当前入栈的操作符与栈内已有操作符的优先级。如果栈内已有操作符的优级高于当前入栈的操作符时，则先依次弹出栈内操作符，并将弹出的内容输出为后缀表达式的一部分，直至栈内操作符的优级低于当前需要入栈的操作符；
4、如果读取一个右括号，则将之前入栈的元素弹出，将弹出的操作符作为后缀表达式的一部分输出，直到遇到左括号为止；
5、上述弹栈时，如果遇到左括号，则只弹出，弹出的内容不作为后缀表达式的一部分；
6、中缀表达式读取完毕后，依次弹出栈内操作符，并将其作为后缀表达式的一部分输出；
/******************
* Author: Wayne Wang
* Modified: Aug 22
*
*
*/
#include#include#include#include
#define MAX_LEN 256
#define ELEMENT_TYPE_VALUE 0
#define ELEMENT_TYPE_OP 1
#define STACK_END_FLAG '#'
typedef union rpn_element{
float value;
char op;
}rpn_element_u;
typedef struct {
rpn_element_u value;
int type;
}rpn_element_t;
typedef struct __rpnList__{
rpn_element_u value;
int type;
struct __rpnList__ *next;
}rpn_element_list_t;
typedef struct {
char *name;
float value;
}rpn_var_t;
typedef struct {
char *data;
int len;
}rpn_str_t;
typedef struct __stack__{
rpn_element_u value;
int type;
struct __stack__ *next;
}rpn_stack_t;
rpn_var_t vars[] = {{"one",1.2},{"two",2.3},{"three",3.4},{"four",4.5},{"five",5.6}};
void rpn_init(rpn_stack_t **s);
void rpn_free_list(rpn_element_list_t *node);
void rpn_push(rpn_stack_t **s,rpn_element_t *e);
void rpn_pop(rpn_stack_t **s, rpn_element_t **e);
int rpn_getoplevel(char op);
void rpn_print_list(rpn_element_list_t *node);
int build_rpn_exprss(char *express,rpn_element_list_t **list);
int rpn_cac_express(rpn_element_list_t *node,float *ret);
int main(void){
rpn_element_list_t *list;
float value;
char *express = "(one+five) + ((four-two)+ 2)*three=\0";
if(build_rpn_exprss(express,&list) == 0){
rpn_print_list(list);
}
else{
printf("build RPN error");
}
rpn_cac_express(list,&value);
printf("Answer: %f",value);
return 0;
}
