一、题目链接
http://codeforces.com/gym/100198/problem/G
二、题意
看样例就能明白，写表达式解析器。
三 、思路
一看这题目，立马就会想到“后缀表达式”，考虑到这里有变量，在把中缀表达式变为后缀表达式时，把变量替换成常量即可。注意，define 2 3 表示，下面的2用3来替换。和C语言是一样的。
PS：然而，我用Java写的，总是RE在第四个样例，实在找不到哪里抛异常了。各位同行，如果您能找到我的代码的bug，烦请您在评论区留下出bug的样例。谢谢！
四、源代码
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;
public class Main {
static final String digitPattern = "-?\\d+";
static final File fin = new File("plcool.in");
static final File fout = new File("plcool.out");
static String input;
static ArrayList<String> inExp = new ArrayList<String>();
static ArrayList<String> postExp = new ArrayList<String>();
static Map<Character, Integer> prior = new HashMap<Character, Integer>();
static Map<String, String> define = new HashMap<String, String>();
static InputStream is = null;
static PrintStream ps = null;
static {
prior.put('^', 3);
prior.put('*', 2);
prior.put('/', 2);
prior.put('%', 2);
prior.put('+', 1);
prior.put('-', 1);
prior.put('(', 0);
prior.put(')', 0);
}
static String findRoot(String key) {
if(!define.containsKey(key))return key;
else return findRoot(define.get(key));
}
static int power(int x, int y) {
int res = 1;
while(y > 0) {
if((y & 1) == 1)res *= x;
x = x * x;
y >>= 1;
}
return res;
}
static int mod(int x, int y) {
int sign = ((x >>> 31) ^ (y >>> 31)) == 0 ? 1 : -1;
return (Math.abs(x) % Math.abs(y)) * sign;
}
static void split() {
inExp.clear();
int s = 0, t = 0, len = input.length();
boolean befOper = false;
for (int i = 0; i < len; ++i) {
if(Character.isDigit(input.charAt(i)) || (input.charAt(i) == '-' && (befOper || i == 0))) {
for(s = i++;i < len && Character.isDigit(input.charAt(i)); ++i);
inExp.add(input.substring(s, i));
--i;
befOper = false;
}
else if(Character.isLetter(input.charAt(i))) {
for(s = i;i < len && (Character.isLetter(input.charAt(i))
|| Character.isDigit(input.charAt(i))); ++i);
inExp.add(input.substring(s, i));
--i;
}
else if(prior.containsKey(input.charAt(i))) {
inExp.add(input.charAt(i) + "");
befOper = true;
}
}
//inExp.forEach(e -> ps.print(e + " "));
for (int i = 0, sz = inExp.size(); i < sz; ++i) {
String now = inExp.get(i);
if (define.containsKey(now)) {
String root = findRoot(now);
if(!root.matches(digitPattern))root = "0";
inExp.set(i, root);
}
else if(!prior.containsKey(now.charAt(0)) && !now.matches(digitPattern))inExp.set(i, "0");
}
//inExp.forEach(e -> ps.print(e + " "));
}
static Stack<Character> opers = new Stack<Character>();
static void toPost() {
opers.clear();
postExp.clear();
for (String s : inExp) {
if (s.matches(digitPattern))
postExp.add(s);
else {
if (opers.isEmpty())
opers.push(s.charAt(0));
else {
char top = opers.peek();
char c = s.charAt(0);
if (s.equals(")")){
while (!opers.isEmpty() && opers.peek() != '(') {
postExp.add(opers.pop() + "");
}
if (!opers.isEmpty() && opers.peek() == '(')
opers.pop();
}
else if((c != '(' && c != '^' && prior.get(c) <= prior.get(top))){
for(top = opers.peek();prior.get(c) <= prior.get(top);) {
postExp.add(opers.pop() + "");
if(!opers.isEmpty())top = opers.peek();
else break;
}
opers.push(c);
}
else
opers.push(c);
}
}
}
while(!opers.isEmpty()) {
char c = opers.pop();
if(c == ')')continue;
else postExp.add(c + "");
}
//postExp.forEach(e -> ps.print(e + " "));
}
static Stack<Integer> digits = new Stack<Integer>();
static int calcResult() {
digits.clear();
for(String s : postExp) {
if(s.matches(digitPattern))digits.push(Integer.parseInt(s));
else {
char c = s.charAt(0);
int last1 = digits.pop(), last2 = digits.pop();
switch (c) {
case '-':{
digits.push(last2 - last1);
break;
}
case '+':{
digits.push(last2 + last1);
break;
}
case '*':{
digits.push(last2 * last1);
break;
}
case '/':{
digits.push(last2 / last1);
break;
}
case '%':{
digits.push(mod(last2, last1));
break;
}
case '^':{
digits.push(power(last2, last1));
break;
}
}
}
}
return digits.pop();
}
static String[] parts;
public static void main(String[] args) throws Exception {
// is = new FileInputStream(fin);
// ps = new PrintStream(new FileOutputStream(fout));
is = System.in;
ps = System.out;
Scanner scanner = new Scanner(is);
while (scanner.hasNextLine()) {
input = scanner.nextLine().trim().toLowerCase();
if (input.charAt(0) == 'p') {
input = input.replaceAll(" ", "");
input = input.substring(5);
split();
toPost();
int res = calcResult();
ps.println(res);
}
else {
parts = input.split(" ");
if (define.containsKey(parts[1]))
continue;
else {
String root1 = findRoot(parts[1]);
String root2 = findRoot(parts[2]);
if(!root1.equals(root2))define.put(parts[1], parts[2]);
}
}
}
scanner.close();
}
}