http://acm.hdu.edu.cn/showPRoblem.php?pid=1237
Problem Description 读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。
Input 测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。
Output 对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。
Sample Input 1 + 2 4 + 2 * 5 - 7 / 11 0
Sample Output 3.00 13.36
这题直接计算的话，因为有优先级的问题，会很麻烦，但是用逆波兰表达式会很简单。
以下解释转自博客：http://blog.csdn.net/geniusluzh/article/details/8192780，但原文有个小错误，在这里已更正，用加粗字体标出 中缀表达式转换为后缀表达式（逆波兰表达式）： 从左至右遍历一个给定的中序表达式，也就是我们常规的数学计算的表达式。 1. 如果遇到的是数字，我们直接加入到栈S1中； 2. 如果遇到的是左括号，则直接将该左括号加入到栈S2中； 3. 如果遇到的是右括号，那么将栈S2中的运算符一次出栈加入到栈S1中，直到遇到左括号，但是该左括号出栈S2并不加入到栈S1中； 4. 如果遇到的是运算符，包括单目运算符和双目运算符，我们按照下面的规则进行操作： - 1. 如果此时栈S2为空，则直接将运算符加入到栈S2中； - 2. 如果此时栈S2不为空，当前遍历的运算符的优先级大于等于栈顶运算符的优先级，那么直接入栈S2； - 3. 如果此时栈S2不为空，当前遍历的运算符的优先级小于等于栈顶运算符的优先级，则将栈顶运算符一直出栈加入到栈S1中，直到栈为空或者遇到一个运算符的优先级小于当前遍历的运算符的优先级，此时将该运算符加入到栈S2中； 5. 直到遍历完整个中序表达式之后，栈S2中仍然存在运算符，那么将这些运算符依次出栈加入到栈S1中，直到栈为空。
求逆波兰表达式的值： 维护一个数据结果栈S3，我们将会看到该栈中最后存放的是最终的表达式的值。我们从左至右的遍历栈S1，然后按照下面的规则进行操作栈S3. 1. 如果遇到的是数字，那么直接将数字压入到S3中； 2. 如果遇到的是单目运算符，那么取S3栈顶的一个元素进行单目运算之后，将结果再次压入到栈S3中； 3. 如果遇到的是双目运算符，那么取S3栈顶的两个元素进行，首先出栈的在右，后出栈的在左，进行双目运算符的计算，将结果再次压入到S3中。 按照上面的三个规则，遍历完整个栈S1，那么最后S3中的值就是逆波兰表达式的值了
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int, int> P;const int N = 1010;int precedence(char ch){ if(ch == '+' || ch == '-') return 1; else if(ch == '*' || ch == '/') return 2; else if(ch == '%' || ch == '^') return 3; else return 0;}void reverse_polish(char s1[], char s2[]){ char st[N]; int k = 0, top = 0; st[top++] = '@'; //在栈底设置一个哨兵位 for(int i = 0; s1[i]; i++) { if(s1[i] == '(') st[top++] = s1[i]; //遇到左括号直接入栈 else if(s1[i] == ')') { //遇到右括号，把st栈中的元素弹出压到s2栈中，指导遇到左括号 while(st[--top] != '(') s2[k++] = st[top]; } else if(s1[i] == '+' || s1[i] == '-' || s1[i] == '*' || s1[i] == '/') { //把当前运算符与st栈顶的运算符比较，栈顶的运算符优先级大于等于当前运算符，就弹出压到s2栈中，直到不符合条件 while(precedence(st[top-1]) >= precedence(s1[i])) s2[k++] = st[--top]; st[top++] = s1[i]; //把当前运算符压到st栈中 } else if(s1[i] >= '0' && s1[i] <= '9') //数字直接压到s2栈中 { while((s1[i] >= '0' && s1[i] <= '9') || s1[i] == '.') s2[k++] = s1[i++]; i--; s2[k++] = ' ';//加空格间隔数字 } } while(st[--top] != '@') s2[k++] = st[top]; //把st栈中剩余元素压到s2栈中 s2[k++] = '/0';}double Operator(double num1, double num2, char ch){ if(ch == '+') return num1 + num2; if(ch == '-') return num1 - num2; if(ch == '*') return num1 * num2; if(ch == '/') return num1 / num2;}void solve(char s[]){ double st[N]; int top = 0; for(int i = 0; s[i]; i++) { if(s[i] >= '0' && s[i] <= '9') {//数字直接压到st栈中 int num = 0; while(s[i] >= '0' && s[i] <= '9') num = num * 10 + s[i] - '0', i++; i--; st[top++] = num; } else if(s[i] != ' ') { //遇到二目运算符，从栈中取出两个数进行运算 double num1 = st[--top], num2 = st[--top]; st[top++] = Operator(num2, num1, s[i]); } } printf("%.2f/n", st[0]);}int main(){ char s1[N], s2[N]; while(true) { gets(s1); if(s1[0] == '0' && strlen(s1) == 1) break; reverse_polish(s1, s2); solve(s2); } return 0;}新闻热点
疑难解答
