『西工大-数据结构-NOJ』 008-逆波兰式(耿3.8) 『西北工业大学』

解题思路：

这道题要求将一个正常的算术表达式（中缀表达式），转换成一个逆波兰式（后缀表达式）。 这道题也算是很经典的题了，还是使用了栈的思想，转换思路如下：

1.从左至右扫描一中缀表达式。 2.若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数堆栈 3.若读取的是运算符 ----(1) 该运算符为左括号"("，则直接存入运算符堆栈。 ----(2) 该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止，此时抛弃该左括号。 ----(3) 该运算符为非括号运算符： --------( a ) 若运算符堆栈栈顶的运算符为左括号，则直接存入运算符堆栈。 --------( b ) 若比运算符堆栈栈顶的运算符优先级高，则直接存入运算符堆栈。 --------( c ) 若比运算符堆栈栈顶的运算符优先级低或相等，则输出栈顶运算符到操作数堆栈，直至运算符栈栈顶运算符低于（不包括等于）该运算符优先级,或为左括号，并将当前运算符压入运算符堆栈。 4.当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。

具体操作见代码，代码中有部分注释。

题解代码：

#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 //定义布尔类型 typedef int BOOL; typedef struct node{ char data; struct node *next; }Node; BOOL IsEmpty(Node *S){//判断栈是否为空，空则返回True if(S->next == NULL){ return TRUE; } return FALSE; } void Push(Node *S, char x){//压入栈,头插法压入栈链表 Node *temp = (Node*)malloc(sizeof(Node)); temp->data = x; temp->next = S->next; S->next = temp; } void Pop(Node *S){//弹出栈 Node *temp = S->next; S->next = S->next->next; free(temp); } char GetTopElem(Node *S){//返回栈顶元素 return S->next->data; } //要进行波兰式之间的转换，首先要分为常变量和运算符两部分，对字符型变量直接输出，对运算符考虑其优先级 //判断x是否为字符型变量 BOOL IsAlpha(char x){ if(x>='a'&&x<='z' || x>='A'&&x<='Z'){ return TRUE; } return FALSE; } //判断x1优先级是否小于x2 BOOL IsLower(char x1, char x2){ if(x1=='+' || x1=='-'){ if(x2=='*' || x2=='/' || x2=='('){ return TRUE; } else{ return FALSE; } } else if(x1=='*' || x1=='/'){ if(x2=='('){ return TRUE; } else{ return FALSE; } } else if(x1=='(' || x1=='#'){ return TRUE; } else{ return FALSE; } } //判断x1优先级是否等于x2 BOOL IsEqual(char x1, char x2){ if(x1=='(' && x2==')'){ return TRUE; } return FALSE; } int main(){ //初始化栈链表 Node *S; S = (Node*)malloc(sizeof(Node)); S->next = NULL; Push(S,'#');//以#作为栈底 char c; char Top; BOOL Is_NoStillRightParentheses_Flag = TRUE;//当出现未配合的')'，我们停止录入 //循环，读入字符c while(TRUE){ if(Is_NoStillRightParentheses_Flag){//如果上次出现了右括号，这次继续输出即可，不需要再读入 scanf("%c",&c); } if(c=='\n'){ break; } Is_NoStillRightParentheses_Flag = TRUE;//重置标志位 if(IsAlpha(c)){//如果c为常变量，直接输出 printf("%c",c); } else{//取栈顶元素进行比较 Top = GetTopElem(S); if(IsEqual(Top,c)){//逆波兰式表达不需要括号，括号完成匹配后直接弹出即可 Pop(S); } else if(IsLower(Top,c)){//如果原栈顶元素优先级更小，将新运算符压栈 Push(S,c); } else{//如果原栈顶元素优先级更大，则栈顶元素将被输出，栈顶元素刷新后，标志位启用，下次继续判断新的栈顶元素是否需要被输出 printf("%c",Top); Pop(S); Is_NoStillRightParentheses_Flag = FALSE; } } } //最后输出栈中剩下的运算符 while(!IsEmpty(S) && GetTopElem(S)!='#'){ printf("%c",GetTopElem(S)); Pop(S); } return 0; }