POJ 1686 Lazy Math Instructor(栈)
Description
Input
Output
Sample Input
Sample Output
解题思路:
AC代码:

原题目网址:http://poj.org/problem?id=1686

题目中文翻译:

数学教师懒得在考卷中给一个问题评分，因为这个问题中，学生会为所问的问题提出一个复杂的公式，但是学生可以用不同的形式写出正确的答案，这使得评分非常困难。所以，教师需要计算机程序员的帮助，或许你可以提供帮助。

你应该编写一个程序来阅读不同的公式，并确定它们是否在算术上相同。

Input

输入的第一行包含一个整数N（1 <= N <= 20），即测试用例的数量。在第一行之后，每个测试用例都有两行。一个测试用例由两个算术表达式组成，每个算术表达式在一个单独的行上，最多80个字符。输入中没有空白行。表达式包含以下一项或多项：

单字母变量（不区分大小写）。

单个数字。

相匹配的左括号和右括号。

二元运算符+， - 和*分别用于加，减和乘。

上述符号之间的任意数量的空白或制表符。

注意：表达式在语法上是正确的，并且从左到右以所有运算符的优先级相同（优先级）进行计算。变量的系数和指数保证适合16位整数。

Output

您的程序必须为每个测试用例输出一行。如果每个测试数据的输入表达式在算术上相同，则必须打印“YES”，否则必须打印“NO”为程序输出。输出应全部使用大写字母。

Sample Input

(a+b-c)*2

(a+a)+(b*2)-(3*c)+c

a*2-(a+c)+((a+c+e)*2)

3*a+c+(2*e)

(a-b)*(a-b)

(a*a)-(2*a*b)-(b*b)

Sample Output

YES

解题思路:

本题要求两个表达式是否相等,而C++无法将数字与字母一起运算,那么我们很容易想到用一个数字代替字母.只要想到这一点,那么这个题的思路就明了了.先逆波兰一遍,再运算就可以了.

AC代码:

 1 #include<cstdio>
 2 #include<map> 
 3 #include<cctype>
 4 #include<iostream>
 5 #include<stack>
 6 #include<string>
 7 
 8 using namespace std;
 9 
10 map<char ,int> m;
11 string s1,s2,r1,r2;
12 
13 string nibolan(string l) {//逆波兰过程 
14     int len = l.length(),i,j;
15     char c[81];
16     stack<char > p;
17     for(i = j = 0;i <= len; i++) {
18         if(isalnum(l[i])) c[j++] = l[i];
19         else {
20             switch(l[i]) {
21                 case '(':
22                     p.push(l[i]);
23                     break;
24                 case ')':
25                     while(p.top() != '(') {
26                         c[j++] = p.top();
27                         p.pop();
28                     }
29                     p.pop();
30                     break;
31                 case '+':
32                 case '-':
33                 case '*':
34                     while(!p.empty() && m[l[i]] <= m[p.top()]) {
35                         c[j++] = p.top();
36                         p.pop();
37                     }
38                     p.push(l[i]);
39             }
40         }
41     }
42     while(!p.empty()) {
43         c[j++] = p.top();
44         p.pop();
45     }
46     c[j] = '

POJ 1686 Lazy Math Instructor(栈) Description Input Output Sample Input Sample Output 解题思路: AC代码: