d char Precede(char c1, char c2)i if(C1==+&&c2=="+) return">’;, 2 # else switch(Precede (get Top(SOP),c)) case '< Push(SOP, c);c=expr[i++]; break case =: Pop (SOP, c);c=expri++]; break case '>: char theta; Pop(SoP, theta) int a, b; Pop (SvAL, b); Pop(SvAl, a; Push(SVAL, Operate(a, theta, b);break; int Operate(int a, char c, int b)i if (c=='+') return a+b; expr s1 AL); 2021/1/29 数据结构及其算法第4章栈和队列
•算法4.16 2021/1/29 数据结构及其算法 第4章 栈和队列 17 int EvaluateExpression(char *expr) { Stack SOP, SVAL; InitStack(SOP); Push(SOP, '#'); InitStack(SVAL); expr[strlen(expr)] = '#'; char tmp[2]; int i=0; char c=expr[i++]; while (c != '#' || GetTop(SOP) != '#') { if (!IsOperator(c)) { tmp[0] = c; tmp[1] = '\0'; Push(SVAL, atoi(tmp)); c = expr[i++]; } else switch(Precede(GetTop(SOP), c)) { case '<': Push(SOP, c); c = expr[i++]; break; case '=': Pop(SOP, c); c = expr[i++]; break; case '>': char theta; Pop(SOP, theta); int a, b; Pop(SVAL, b); Pop(SVAL, a); Push(SVAL, Operate(a, theta, b)); break; } } expr[strlen(expr)] = '\0'; return GetTop(SVAL); } bool IsOperator(char c) { return c == '+' || c == '-' ... } char Precede(char c1, char c2) { if (c1 == '+' && c2 == '+') return '>'; ... } int Operate(int a, char c, int b) { if (c == '+') return a+b; ... }
种表达式 表达式前缀( prefix)表达中缀( infix)表达式后缀( postfix)表达 别名波兰式(PO1ish 逆波兰式( Reverse notation) Polish notation) 特点运算符在操作数之前运算符在操作数中间运算符在操作数之后 需要括号表示优先级 例 大a+bC a*(b+c) abC+大 表达式的相互转换 如4×2+(7-8÷2)转为逆波兰式:42×782÷-+ ·逆波兰式中,运算符的出现顺序决定了运算顺序 将中缀表达式转为逆波兰式,可以用操作符栈来实现 对逆波兰式求值,可以用操作数栈来实现 2021/1/29 数据结构及其算法第4章栈和队列
•三种表达式 •表达式的相互转换 • 如4×2+(7-8÷2)转为逆波兰式：42×782÷-+ • 逆波兰式中，运算符的出现顺序决定了运算顺序 • 将中缀表达式转为逆波兰式，可以用操作符栈来实现 • 对逆波兰式求值，可以用操作数栈来实现 2021/1/29 数据结构及其算法 第4章 栈和队列 18 表达式 前缀(prefix)表达 式 中缀(infix)表达式 后缀(postfix)表达 式 别名 波兰式(Polish notation) 逆波兰式(Reverse Polish notation) 特点 运算符在操作数之前 运算符在操作数中间 需要括号表示优先级 运算符在操作数之后 例 *a+bc a*(b+c) abc+*