Written by razrlele
19:04 September 29, 2015
Lazy Math Instructor
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 3766 | Accepted: 1307 |
Description
A math instructor is too lazy to grade a question in the exam papers in which students are supposed to produce a complicated formula for the question asked. Students may write correct answers in different forms which makes grading very hard. So, the instructor needs help from computer programmers and you can help.
You are to write a program to read different formulas and determine whether or not they are arithmetically equivalent.
Input
The first line of the input contains an integer N (1 <= N <= 20) that is the number of test cases. Following the first line, there are two lines for each test case. A test case consists of two arithmetic expressions, each on a separate line with at most 80 characters. There is no blank line in the input. An expression contains one or more of the following:
- Single letter variables (case insensitive).
- Single digit numbers.
- Matched left and right parentheses.
- Binary operators +, – and * which are used for addition, subtraction and multiplication respectively.
- Arbitrary number of blank or tab characters between above tokens.
Note: Expressions are syntactically correct and evaluated from left to right with equal precedence (priority) for all operators. The coefficients and exponents of the variables are guaranteed to fit in 16-bit integers.
Output
Your program must produce one line for each test case. If input expressions for each test data are arithmetically equivalent, “YES”, otherwise “NO” must be printed as the output of the program. Output should be all in upper-case characters.
Sample Input
1 2 3 4 5 6 7 |
3 (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
1 2 3 |
YES YES NO |
Source
题意
就是比较中缀表达式是否相等,题目中的字母直接用ASCII码来替换,然后看题目的数据的话,比较的只是表达式的最终数值大小,而不是比较表达式是否完全相等,比如a+1和90+8在测试数据中是算两个相等的表达式。
思路
首先把中缀表达式转换成后缀表达式,转换的时候维护一个操作符栈,然后如果优先级大于栈顶就压栈,小于或等于就一直出栈直到当前输入符优先级大于栈顶元素,'(‘优先级最低,直接入栈,碰到’)’才出栈,但是不输出到结果串,然后再计算后缀表达式的值,主要就是用到了栈。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 |
/* * File Name: poj1686.cpp * Author: razrLeLe * Mail: razrlele@gmail.com */ #include <vector> #include <set> #include <deque> #include <queue> #include <algorithm> #include <functional> #include <iostream> #include <cstdio> #include <cmath> #include <cstdlib> #include <string> #include <cstring> #include <string.h> #include <map> #include <cctype> #include <list> #include <stack> #define forn(i, m, n) for (int i = int(m); i < int(n); i++) typedef long long ll; using namespace std; #define INF 0x3f3f3f3f //#define LOCAL map<char, int> priority; bool compare(char a, char b) { return priority[a] > priority[b]; } string InfixToRPN(string instr) { int len = instr.length(); string result = ""; stack<char> op; for (int i = 0; i < len; i++) { if (isalpha(instr[i]) || instr[i] >= '0' && instr[i] <= '9') result = result + instr[i]; else if (instr[i] != ' ') { if (instr[i] == '(' || op.empty()) op.push(instr[i]); else if (instr[i] == ')') { while (op.top() != '(') { result = result + op.top(); op.pop(); } op.pop(); } else if (compare(instr[i], op.top())) op.push(instr[i]); else if (!compare(instr[i], op.top())) { while (!compare(instr[i], op.top())) { result = result + op.top(); op.pop(); if (op.empty()) break; } op.push(instr[i]); } } } while (!op.empty()) { result = result + op.top(); op.pop(); } return result; } int calculate(string instr) { int len = instr.length(); stack<int> ans; int num1, num2; for (int i = 0; i < len; i++) { if (instr[i] >= '0' && instr[i] <= '9') ans.push(instr[i] - '0'); else if (isalpha(instr[i])) ans.push(instr[i]); else { num1 = ans.top(); ans.pop(); num2 = ans.top(); ans.pop(); switch (instr[i]) { case '+': num2 += num1; break; case '-': num2 -= num1; break; case '*': num2 *= num1; break; default: break; } ans.push(num2); } } return ans.top(); } int main(int argc, char** argv) { #ifdef LOCAL freopen("/home/razrlele/build/data.txt", "r", stdin); freopen("/home/razrlele/build/out.txt", "w", stdout); #endif int n; cin >> n; getchar(); priority['*'] = 2; priority['+'] = 1; priority['-'] = 1; priority['('] = 0; while (n--) { int ans1, ans2; string instr; getline(cin, instr); ans1 = calculate(InfixToRPN(instr)); getline(cin, instr); ans2 = calculate(InfixToRPN(instr)); if (ans1 == ans2) cout << "YES" << endl; else cout << "NO" << endl; } return 0; } |