解題區/解題區 - UVa

UVa 198 - Peter's Calculator

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Problem

Unfortunately, Peter’s Calculator broke down last week. Now Peter is left with his computer, which has no calculator application, and paper and pencil, which is too tiresome for an engineer. As one of Peter’s friends, you are asked to write him a calculator application. After talking to him, you figure out the following:

  • Peter does only integer arithmetic. The operations he needs are addition, subtraction and multiplication.
  • He would like to use an arbitrary number of variables whose names are not longer than 50 characters.
  • His main way of doing calculations are to type in a few formulas and to assign them to variables. Some formulas are complicated expressions, which can refer to yet undefined variables, while other formulas consist of a single number. Then Peter asks for the value of some variables, i.e. he evaluates the formulas.
  • Peters wants to redefine some variables and then to reevaluate formulas that depend on these variables.

The input strictly adheres to the following syntax (given in EBNF):

1
2
3
4
5
6
7
8
9
10
file = line { line } <EOF>.
line = [ assignment | print | reset ] <CR>.
assignment = var ":=" expression.
print = "PRINT" var.
reset = "RESET".
expression = term { addop term }.
term = factor { mulop factor }.
factor = "(" expression ")" | var | number.
addop = "+" | "-".
mulop = "*".

In the Extended Backus-Naur Formalism (EBNF), A = B C declares that the grammatical construct A consists of a B followed by a C . A = B | C means that A consists of a B or, alternatively, of a C . A = [ B ] defines construct A to be either a B or nothing and A = B tells you that A consists of the concatenation of any number of B’s (including none).

The production var stands for the name of a variable, which starts with a letter followed by up to 49 letters or digits. Letters may be uppercase or lowercase. The production number stands for a integer number. The precise syntax for these productions are given below. The case of letters is important for both variables and statements.

1
2
3
4
var = letter { letter | digit }.
number = [ "-" ] digit { digit }.
letter = "A" | "B" | ... | "Z" | "a" | "b" | ... | "z".
digit = "0" | "1" | ... | "8" | "9".

Between the parts of a grammatical construct but not within the names of variables or integer numbers, any number of spaces may appear. stands for the end of the input file and stands for the new-line character. All lines in the input file are shorter than 200 characters.

The value of a variable is said to be undefined:

  • if it has not yet been defined or it refers to a variable, which has not yet been defined;
  • if the definition of the variable contains a cycle.

Your are to write a program that implements Peter’s calculator. It should store all variable definitions and for each “PRINT” statement evaluate the specified variable based on the latest variable definitions. If your program encounters a “RESET” statement, it should delete all stored variables so that all variables become undefined.

Input

The input file contains calculations adhering to the syntax given above. Each line contains either an assignment to a variable, a “PRINT” statement, a “RESET” statement or nothing.

Output

For each “PRINT” statement found in the input file, your program should output a line containing the numerical value of the specified variable or the word “UNDEF” if the variable is undefined.

Sample Input

1
2
3
4
5
6
7
8
9
a := b + c
b := 3
c := 5
PRINT d
PRINT a
b := 8
PRINT a
RESET
PRINT a

Sample Output

1
2
3
4
UNDEF
8
13
UNDEF

Solution

題目描述：

輸入有一連串的變數函數，適時地打印出詢問的變數值，如果存在循環依靠 (無法推論) 或者是變數尚未定義，直接輸出 UNDEF。

後輸入的變數函數會覆蓋原先的函數。

題目解法：

將每一組函數轉成後序運算式子，爾後再使用深度優先搜索走訪查看是否有環。

著重的問題在於負數的分析，例如 0 - -50, (a + b) - 50 等等。

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <stdio.h>
#include <stack>
#include <string.h>
#include <algorithm>
#include <ctype.h>
#include <iostream>
#include <sstream>
#include <map>
using namespace std;
int priority_op(char c) {
    switch(c) {
        case '(':return 0;
        case '+': case '-':return 1;
        case '*': case '/':return 2;
    }
    return -1;
}
int isoperator(char c) {
    switch(c) {
        case '(':case ')':case '+': case '-':case '*': case '/':return 1;
    }
    return 0;
}
int isvariable(string token) {
    return isalpha(token[0]);
}
void trans(const char *infix, char buffer[]) {
    int len = strlen(infix), prevOp = 1;
    char *ptr = buffer;
    stack<char> op;
    *ptr = '\0';
    for(int i = 0; i < len; i++) {
        if(isalpha(infix[i]) || isdigit(infix[i]) 
            || (infix[i] == '-' && isdigit(infix[i+1]) && prevOp)) {
            prevOp = 0;
        	sprintf(ptr, "%c", infix[i]), i++;
        	while(*ptr)    ptr++;
            while(isalpha(infix[i]) || isdigit(infix[i])) {
            	sprintf(ptr, "%c", infix[i]), i++;
            	while(*ptr)    ptr++;
            }
            sprintf(ptr, " "), i--;
            while(*ptr)		ptr++;
        } else {
        	prevOp = 0;
            if(infix[i] == ')') {
                while(!op.empty() && op.top() != '(') {
                    sprintf(ptr, "%c ", op.top()), op.pop();
                    while(*ptr) ptr++;
                }
                op.pop();
            } else {
                if(infix[i] != '(') {
                    while(!op.empty() && priority_op(op.top()) >= priority_op(infix[i])) {
                        sprintf(ptr, "%c ", op.top()), op.pop();
                        while(*ptr) ptr++;
                    }
            	}
            	prevOp = 1;
                op.push(infix[i]);
            }
        }
    }
    while(!op.empty()) {
        sprintf(ptr, "%c ", op.top()), op.pop();
        while(*ptr) ptr++;
    }
}
void trimWhiteSpace(char s[]) {
    int j = 0;
    for(int i = 0; s[i]; i++)
        if(!isspace(s[i]))
            s[j++] = s[i];
    s[j] = '\0';
}
map<string, string> VAL_exp;
map<string, int>	VAL_val;
map<string, int>	VAL_stk;
int error_FLAG;
int calcPostfix(const char* postfix);
int getValue(string VAL_name) {
    if(!isvariable(VAL_name)) {
    	stringstream scin(VAL_name);
    	int value;
    	scin >> value;
    	return value;
    }
    if(VAL_exp.find(VAL_name) == VAL_exp.end() || VAL_stk[VAL_name]) {
        error_FLAG = 1;
        return 0;
    }
    if(VAL_val.find(VAL_name) == VAL_val.end()) {
        VAL_stk[VAL_name] = 1;
//		cout << "solving " << VAL_name << ", " << VAL_exp[VAL_name] << endl; 
        VAL_val[VAL_name] = calcPostfix(VAL_exp[VAL_name].c_str());
//		cout << "solved " << VAL_name << ", val = " << VAL_val[VAL_name] << endl;
        VAL_stk[VAL_name] = 0;
    }
    return VAL_val[VAL_name];
}
int calcPostfix(const char* postfix) {
    stringstream 	scin(postfix);
    stack<int> 		stk;
    string			token;
    int 			a, b;
    
    while(scin >> token) {
    	if(token.length() == 1 && isoperator(token[0])) {
            b = stk.top(), stk.pop();
            a = stk.top(), stk.pop();
            switch(token[0]) {
                case '+': a = a+b;break;
                case '-': a = a-b;break;
                case '*': a = a*b;break;
                case '/': a = a/b;break;
            }
            stk.push(a);
    	} else {
    		stk.push(getValue(token));
    	}
    	if(error_FLAG)	return 0;
    }
    return stk.top();
}
void printVal(string valName) {
    error_FLAG = 0;
    VAL_val.clear();
    VAL_stk.clear();
    int val = getValue(valName);
    if(error_FLAG)
        puts("UNDEF");
    else
        printf("%d\n", val);
}
int main() {
//	freopen("input.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    string 	LHS, RHS;
    int 	pos;
    char 	postfix[32767], lines[32767];
    
    while(gets(lines)) {
    	trimWhiteSpace(lines);
    	string str(lines);
    	if(str.find(":=") != string::npos) {
    		pos = str.find(":=");
    		LHS = str.substr(0, pos);
    		RHS = str.substr(pos + 2);
    		trans(RHS.c_str(), postfix);
    		VAL_exp[LHS] = postfix;
    	} else if(str.find("PRINT") != string::npos) {
    		pos = str.find("PRINT");
    		RHS = str.substr(pos + 5);
    		printVal(RHS);
    	} else if(str.find("RESET") != string::npos) {
    		VAL_exp.clear();
    	}
    }
    return 0;
}