解題區/解題區 - UVa

UVa 172 - Calculator Language

contents

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

Problem

Calculator Language (CL) supports assignment, positive and negative integers and simple arithmetic. The allowable characters in a CL statement are thus:

All operators have the same precedence and are right associative, thus 15 - 8 - 3 = 15 - (8 - 3) = 10. As one would expect, brackets will force the expression within them to be evaluated first. Brackets may be nested arbitrarily deeply. An expression never has two operators next to each other (even if separated by a bracket), an assignment operator is always immediately preceded by a variable and the leftmost operator on a line is always an assignment. For readability, spaces may be freely inserted into an expression, except between a negative sign and a number. A negative sign will not appear before a variable. All variables are initialised to zero (0) and retain their values until changed explicitly.

Write a program that will accept and evaluate expressions written in this language. Each expression occupies one line and contains at least one assignment operator, and maybe more.

Input

Input will consist of a series of lines, each line containing a correct CL expression. No line will be longer than 100 characters. The file will be terminated by a line consisting of a single #.

Output

Output will consist of a series of lines, one for each line of the input. Each line will consist of a list of the final values of all variables whose value changes as a result of the evaluation of that expression. If more than one variable changes value, they should be listed in alphabetical order, separated by commas. If a variable changes value more than once in an expression, only the final value is output. A variable is said to change value if its value after the expression has been evaluated is different from its value before the expression was evaluated. If no variables change value, then print the message `No Change’. Follow the format shown below exactly.

Sample input

1
2
3
4
5
6
7
A = B = 4
C = (D = 2)*_2
C = D = 2 * _2
F = C - D
E = D * _10
Z = 10 / 3
#

Sample output

1
2
3
4
5
6
A = 4, B = 4
C = -4, D = 2
D = -4
No Change
E = 40
Z = 3

Solution

題目描述：

給一個六則運算，並且所有運算由右往左，也就是題目提及的 right associative，並且在每一個運算式之後輸出有改變值的變數結果。

題目解法：

要處理的問題相當多，按照一般的思路要做出 right associative 還不打緊，就像冪次的定義一樣，也就是把 stack 的嚴格遞增改成非嚴格遞增。

但是查閱討論區給定的數據後，如下所示

範例輸入

1
2
B=(A=1)+(A=2)
#

範例輸出

1
A = 1, B = 3

這表示著連括弧運算順序都是 right associative，這一點相當苦惱，於是最後建造 tree，然後先拜訪右子樹、再拜訪左子樹來解決這些問題。

中間誤把 No Change 寫成 No change，因此卡了不少 Wrong Answer。

Sample Input:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
A = B = 4
B=B-6+B=100
C = (D = 2) * _2
C = D = 2 * _2
E = D * _10
F = 15 - 8 - 3
F = 15 - 8 + _3
F=1+F=F-1
A=((3))
Z=Y=X=A=B=C=1+D=E=F=G=2-H=K=J=I=L=M=O=N=P=Q=R=S=T=V=U=W=3
A=100/2
A=100/_2
B=(_1+A*2)/2
B=(1+A*_2)/2
A=(((1-2)*3)+4)
A=((1-(2*3))+4)
A=((1-2)*(3+4))
A=(1-(2*(3+4)))
A=1+2+1+1+1+1+1+1+1+1+1+1+1+1+1+11+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+3
#

AC Sample Output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
A = 4, B = 4
B = -6
C = -4, D = 2
D = -4
E = 40
F = 10
No Change
No Change
A = 3
A = 0, B = 0, C = 0, D = -1, E = -1, F = -1, G = -1, H = 3, I = 3, J = 3, K = 3, L = 3, M = 3, N = 3, O = 3, P = 3, Q = 3, R = 3, S = 3, T = 3, U = 3, V = 3, W = 3
A = 50
A = -50
B = -50
B = 50
A = 1
A = -1
A = -7
A = -13
A = 62

一開始還在想為什麼當 B = 4 時，B=B-6+B=100 會產出 B = -6，由右往左運算。

  • B = 100
  • 6 + B = 106
  • B - (6 + B) = 100 - 106 = -6
  • B assign(=) -6
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
161
162
163
164
165
166
167
168
169
170
171
// Accepted
#include <stdio.h>
#include <stack>
#include <string.h>
#include <algorithm>
#include <ctype.h>
#include <iostream>
#include <sstream>
using namespace std;
int priority_op(char c) {
    switch(c) {
        case '(':return -1;
        case '=':return 3;
        case '+': case '-':return 1;
        case '*': case '/':return 2;
    }
    puts("ERROR");
    return -1;
}
void trans(char infix[], char buffer[]) {
    int len = strlen(infix);
    char *ptr = buffer;
    stack<char> op;
    *ptr = '\0';
    for(int i = 0; i < len; i++) {
        if(infix[i] == '_' || isdigit(infix[i]) || isalpha(infix[i])) {
        	while(infix[i] == '_' || isdigit(infix[i]) || isalpha(infix[i])) {
        		if(infix[i] == '_')
        			sprintf(ptr, "-");
        		else
            		sprintf(ptr, "%c", infix[i]);	
            	while(*ptr)    ptr++;
            	i++;
        	}
            sprintf(ptr, " ");	
            while(*ptr)    ptr++;
        	i--;
        }else {
        	if(infix[i] == ' ')	continue;
            if(infix[i] == ')') {
                while(!op.empty() && op.top() != '(') {
                    sprintf(ptr, "%c ", op.top()), op.pop();
                    while(*ptr) ptr++;
                }
                op.pop();
            } else {
                if(infix[i] != '(') {
                	if(infix[i] == '=') {
                		while(!op.empty() && priority_op(op.top()) > priority_op(infix[i])) {
                    		sprintf(ptr, "%c ", op.top()), op.pop();
                    		while(*ptr) ptr++;
                		}
                	} else {
                		while(!op.empty() && priority_op(op.top()) > priority_op(infix[i]) && op.top() != '=') {
                    		sprintf(ptr, "%c ", op.top()), op.pop();
                    		while(*ptr) ptr++;
                		}
                	}
                }
                op.push(infix[i]);
            }
        }
    }
    while(!op.empty()) {
        sprintf(ptr, "%c ", op.top()), op.pop();
        while(*ptr) ptr++;
    }
}
int Variable[26] = {}, oldVal[26] = {};
string to_string(int number) {
   stringstream ss;//create a stringstream
   ss << number;//add number to the stream
   return ss.str();//return a string with the contents of the stream
}
struct TreeNode {
    string 	A, B, OP;
    int 	l, r;
    TreeNode(string a="", string b="", string op=""):
        A(a), B(b), OP(op) {}
};
TreeNode node[1024];
int runTree(int label) {
    string 	A = node[label].A;
    string	B = node[label].B;
    int 	a, b;
    if(node[label].OP == "LEAF") {
        if(isalpha(A[0]))
           	a = Variable[A[0] - 'A'];
        else
           	a = atoi(A.c_str());
        return a;	
    }
    b = runTree(node[label].r);
    a = runTree(node[label].l);
//	printf("%d %d\n", a, b);
    //cout << A << ", " << B << ", " << node[label].OP << endl;
    switch(node[label].OP[0]) {
    	case '+': a = a + b; break;
        case '-': a = a - b; break;
        case '*': a = a * b; break;
        case '/': a = a / b; break;
        case '=': 
        	a = b;
        	if(isalpha(A[0])) {
        		Variable[A[0] - 'A'] = a;
        		//cout << A << " -- " << a << endl;
        	}
        	break;
    }
    return a;
}
void buildTree(char postfix[]) {
    
    stringstream	sin(postfix);
    string 			token, A, B;
    stack<string>	stk;
    stack<int>		nodeLabel;
    int 			treeSize = 0;
    
    while(sin >> token) {
    	if(isalpha(token[0])) {
    		stk.push(token);
    		nodeLabel.push(treeSize);
    		node[treeSize++] = TreeNode(token, "", "LEAF");
    		
    	} else if(isdigit(token[token.length() - 1])) {
    		stk.push(token);
    		nodeLabel.push(treeSize);
    		node[treeSize++] = TreeNode(token, "", "LEAF");
    	} else {
            B = stk.top(), stk.pop();
            A = stk.top(), stk.pop();
            int a, b;
            b = nodeLabel.top(), nodeLabel.pop();
            a = nodeLabel.top(), nodeLabel.pop();
            nodeLabel.push(treeSize);
            node[treeSize] = TreeNode(A, B, token);
            node[treeSize].l = a, node[treeSize].r = b;
            treeSize++;
            stk.push("INNER");
    	}
    }
    runTree(nodeLabel.top());
}
char infix[262144], postfix[262144];
int main() {
    while(gets(infix) && infix[0] != '#') {
        trans(infix, postfix);
        
        for(int i = 0; i < 26; i++)
        	oldVal[i] = Variable[i];
        	
        buildTree(postfix);
        
        int f = 0;
        for(int i = 0; i < 26; i++) {
        	if(oldVal[i] != Variable[i]) {
        		if(f)	printf(", ");
        		f = 1;
        		printf("%c = %d", i + 'A', Variable[i]);
        	}
        }
        if(f == 0)
        	puts("No Change");
        else
        	puts("");
        //printf("%s\n", postfix);
    }
    return 0;
}