hdoj 1237 简单计算器(计算器应用)

hdoj 1237 简单计算器（计算器应用）

2012-9-26阅读117评论0

转自 Bupt Acmer

任意表达式(expression)都是由操作数(operand)操作符(operator)和界限符(delimiter)组成。我们通常习惯使用中缀表达式(infix expression)，但中缀表达式离不开括号(bracket)。若使用前缀表达式(prefixexpression)或后缀表达式(postfix expression)则不需要括号。利用栈，可以将中缀表达式变为前缀表达式或后缀表达式，再用栈进行运算即可得到表达式的值(value)。为了讨论的方便，在不影响问题实质的情况下，我们对表达式做如下简化：

(1) 假定所有运算分量都是整数；(2) 所有运算符都是整数的二元操作，且都用一个字符表示。 中缀表达式：表达式中所有运算符都出现在它的两个运算分量之间。例如：31 * (5 - 22) + 70

后缀表达式：这种表达式里不再需要有括号，每个运算符都出现在它的两个运算分量后面。例如：31 5 22 - * 70 +

5 * (27 + 3 * 7) + 22 转化为后缀表达式为：5 27 3 7 * + * 22 +

举例：31*(5-22)+70 转换为：31 5 22 - * 70 + 31*(5-22)+70 *(5-22)+70 31 (5-22)+70 * 31 5-22)+70 (* 31 -22)+70 (* 31 5 22)+70 -(* 31 5 )+70 -(* 31 5 22 +70 * 31 5 22 - 70 + 31 5 22 - * + 31 5 22 - * 70 31 5 22 - * 70 + 后缀表达式的主要优点是可以写出非常简单的求值过程。使用一个存放运算分量（数）的栈，求值过程顺序扫描后缀表达式，每次遇到运算分量(数)便将它推入栈中；遇到运算符时，就从栈中弹出两个整数(运算分量)进行计算，而后再把结果推入栈中。这样，到扫描结束时，留在栈顶的整数就是所求表达式的值。

31 5 22 - * 70 + 5 22 - * 70 + 31 22 - * 70 + 5 31 - * 70 + 22 5 31 * 70 + 17 31 70 + 527 + 70 527 457 457 计算结束

以上例子大概可以看到表达式求值的具体过程和算法，总结一下：

有两种方式，先将中缀表达式转换成后缀表达式再用后缀表达式求值，或者直接在转换的过程中求值。

一、 将中缀表达式变为后缀表达式

1.设置一个操作符栈，将“=”压入堆栈；2.逐个字符扫描中缀表达式：3.若当前字符为操作数，直接输出；4.若当前字符为“=”，则将堆栈元素全部退栈并输出，算法结束；5.若当前字符为“）”，则堆栈元素开始退栈并输出，直至遇到“（”，退栈；6.若当前字符为操作符，则将其与栈顶元素比较优先级别：7.若当前操作符的优先级别高于栈顶元素，则将当前操作符压入堆栈；8.否则，就将栈顶元素退栈并输出，转到步骤3继续比较。二、 后缀表达式求值

1.设置一个操作数栈；2.逐个字符扫描后缀表达式：3.若当前字符为“=”，将结果退栈输出，算法结束；4.若当前字符为操作数，则将该操作数压入堆栈；5.否则，当前字符就为操作符，栈顶元素和次栈顶元素退栈，用次栈顶元素“操作”栈顶元素，将运算结果压入堆栈。、三、 中缀表达式求值

1.设置两个堆栈：操作符栈和操作数栈，向操作符栈中压入“=”；2.逐个字符扫描中缀表达式：3.若当前字符为操作数，直接压入操作数栈；4.若当前字符为“=”，则将操作符栈元素全部退栈并执行运算操作，最后将操作数栈元素退栈并输出，算法结束；5.若当前字符为“）”，则操作符栈元素退栈并执行运算操作，直至遇到“（”，退栈；6.若当前字符为操作符，则将其与栈顶元素比较优先级别：7.若当前操作符的优先级别高于栈顶元素，则将当前操作符压入堆栈；8.否则，就将栈顶元素退栈并执行运算操作，转到步骤3继续比较；9.执行元算操作：将操作数栈顶元素和次栈顶元素退栈，用次栈顶元素“操作”栈顶元素，将运算结果压入操作数栈。优先级别：

3---“（”；2---“*”、“/”；1---“+”、“-”； 0---“=”、栈中的“（”。例题分析

hdoj 1237 简单计算器

题目大意

编写一个只有四则运算的计算器

题目分析

没有括号，只有两个优先级的计算器，源码采用了直接从中缀表达式到结果的算法。

题目源码

#include#include#include#include#includeusing namespace std;stack N; //操作数栈 stack O;//操作符栈 double calcul(char oper)//双目运算符 { double a = N.top(), b; N.pop(); b = N.top(); N.pop(); switch(oper){ case '+': return b + a;//加法 case '-': return b - a;//减法 case '*': return b * a;//乘法 case '/': return b / a;//除法 }}int main(){ int len, i; //表达式长度，计数器，数字转换时记录小数位 double num, a, b; char s[210], oper; //表达式，操作符 while (gets(s)){ //读入一行表达式 len = strlen(s); //计算出表达式的长度 if (len == 1 && s[0] == '0') break; i = 0; while (i = '0' && s[i]

题目推荐

同学们可自行扩展，带括号的，乘方运算，对数，取模，三角函数，处理异常错误，浮点计算器等等。

boj 1441寻求帮助poj 1686 Lazy Math Instructor