课本的第一个难点,个人认为是第三章的后缀表达式。这是一个大多数人先前完全没有接触过的运算规则,初次上手难免会有困难。
前置科技:
0.脑子还在脖子上
1.能够建立栈结构并实现基本操作
2.熟悉各运算符优先级
中缀表达式转为后缀表达式的规则,简单总结一下。
首先准备一个栈,用来进行计算操作
0.键入表达式,这里默认用阿拉伯数字和四则运算符以及左右英文括号输入的智力发育正常的一般人类能够理解的正确地数学表达式
- 从左往右扫描表达式,每次取出一个字符
- 若该项为操作数,则直接输出
- 若为运算符,执行以下步骤
- 若栈为空栈或栈顶为 ( 左括号,则该运算符入栈
- 栈顶为运算符且其优先级更低,该运算符入栈
- 栈顶运算符优先级更高或相同,则该项暂不入栈,弹出栈顶元素并输出,重复4~6
- 若该项为左括号( ,则直接入栈
- 若为右括号) ,则依次输出栈内元素,直到栈顶为左括号,随后将左括号弹出并丢弃
你已经学会了转换过程,现在试一试上手编译原理吧!
在实际开始编写代码前,用小纸片在桌上摆一摆会更好理解。
添加于3小时后:气死我了!书上的程序是错的!!
下头贴出我拙劣的代码!使用Visual Studio 2017进行编译。
点击可以下载全部源文件:Stack and Postfix.zip
#include"stack.h" int Cpriority(char c); void infixtopostfix() { char ch='\0', y='\0'; Stack M; Stack* s=&M; Create(s,36); printf("输入表达式后请回车\n"); while (ch != '\n') { ch = getchar(); if ((ch >= '0'&&ch <= '9') || (ch >= 'a'&&ch <= 'z')) printf("%c", ch); else if (ch != ')' &&( ch == '(' || isEmpty(s) || (Top(s, &y), y) == '(')) { Push(s,ch); y = '\0'; } else if (ch == ')') { for (Top(s, &y), Pop(s); y != '('; Top(s, &y),Pop(s)) { printf("%c", y); } y = '\0'; } else { for (Top(s, &y), Pop(s); (Cpriority(y) <= Cpriority(ch)); Top(s, &y), Pop(s)) { printf("%c", y); y = '\0'; if (isEmpty(s)) break; } Push(s, y); Push(s, ch); y = '\0'; } } for (Top(s, &y); !isEmpty(s);) { Top(s, &y); Pop(s); printf("%c", y); } } int Cpriority(char c) { int f; switch (c) { case '+':f=4; case '-':f=4; break; case '*':f=3; case '/':f=3; break; case '(':f=-10; break; default:f = 10; } return f; }