uva 327 Evaluating Simple C Expressions
原题：
The task in this problem is to evaluate a sequence of simple C expressions, buy you need not know C
to solve the problem! Each of the expressions will appear on a line by itself and will contain no more
than 110 characters. The expressions to be evaluated will contain only simple integer variables and a
limited set of operators; there will be no constants in the expressions. There are 26 variables which
may appear in our simple expressions, namely those with the names ‘a’ through ‘z’ (lower-case letters
only). At the beginning of evaluation of each expression, these 26 variables will have the integer values
1 through 26, respectively (that is, a = 1, b = 2, …, n = 14, o = 15, …, z = 26). Each variable will
appear at most once in an expression, and many variables may not be used at all.
The operators that may appear in expressions include the binary (two-operand) ‘+’ and ‘-’, with
the usual interpretation. Thus the expression ‘a + c - d + b’ has the value 2 (computed as ‘1 + 3 -
4 + 2’). The only other operators that may appear in expressions are ‘++’ and ‘–’. These are unary
(one-operand) operators, and may appear before or after any variable. When the ‘++’ operator appears
before a variable, that variable’s value is incremented (by one) before the variable’s value is used in
determining the value of the entire expression. Thus the value of the expression ‘++ c - b’ is 2, with
‘c’ being incremented to 4 prior to evaluating the entire expression. When the ‘++’ operator appears
after a variable, that variable is incremented (again, by one) after its value is used to determine the
value of the entire expression. Thus the value of the expression c ++ - b is 1, but ‘c’ is incremented
after the complete expression is evaluated; its value will still be 4. The ‘–’ operator can also be used
before or after a variable to decrement (by one) the variable; its placement before or after the variable
has the same signficance as for the ‘++’ operator. Thus the expression ‘–c + b–’ has the value 4,
with variables ‘c’ and ‘b’ having the values 2 and 1 following the evaluation of the expression.
Here’s another, more algorithmic, approach to explaining the ‘++’ and ‘–’ operators. We’ll consider
only the ‘++’ operator, for brevity:
- Identify each variable that has a ‘++’ operator before it. Write a simple assignment statement
that increments the value of each such variable, and remove the ‘++’ operator from before that
variable in the expression. - In a similar manner, identify each variable that has a ‘++’ operator after it. Write a simple
assignment statement that increments the value of each of these, and remove the ‘++’ operator
from after that variable in the expression. - Now the expression has no ‘++’ operators before or after any variables. Write the statement that
evaluates the remaining expression after those statements written in step 1, and before those
written in step 2. - Execute the statements generated in step 1, then those generated in step 3, and finally the one
generated in step 2, in that order.
Using this approach, evaluating the expression ‘++ a + b ++’ is equivalent to computing ‘a = a +
1’ (from step 1 of the algorithm) ‘expression = a + b’ (from step 3) ‘b = b + 1’ (from step 2) where
expression would receive the value of the complete expression.
Input
Your program is to read expressions, one per line, until the end of the file is reached.
Output
Display each expression exactly as it was read, then display the value of the entire expression, and on
separate lines, the value of each variable after the expression was evaluated. Do not display the value of
variables that were not used in the expression. The samples shown below illustrate the desired exact
output format.
Blanks are to be ignored in evaluating expressions, and you are assured that ambiguous expressions
like ‘a+++b’ (ambiguous because it could be treated as ‘a++ + b’ or ‘a + ++b’) will not appear in the
input. Likewise, ‘++’ or ‘–’ operators will never appear both before and after a single variable. Thus
expressions like ‘++a++’ will not be in the input data.
Sample Input
a + b
b - z
a+b–+c++
c+f–±-a
f-- + c-- + d-++e
Sample Output
Expression: a + b
value = 3
a = 1
b = 2
Expression: b - z
value = -24
b = 2
z = 26
Expression: a+b–+c++
value = 6
a = 1
b = 1
c = 4
Expression: c+f–±-a
value = 9
a = 0
c = 3
f = 5
Expression: f-- + c-- + d-++e
value = 7
c = 2
d = 4
e = 6
f = 5
中文：
给你一个表达式，这个表达式，这个表达式仅由加法和减法组成，其中表达式中的变量会有类似“++a”和“a++”这样的运算符出现。
给定的表达式保证合法，现在问你这个表达式的计算结果是多少，同时输出每个变量在计算完表达式后的值为多少。
注意，会有如下数据
a
++a
–a
a++
a–
结果为：
Expression: a
value = 1
a = 1
Expression: ++a
value = 2
a = 2
Expression: --a
value = 0
a = 0
Expression: a++
value = 1
a = 2
Expression: a–
value = 1
a = 0
代码：
#include <bits/stdc++.h>
using namespace std;
struct node
{
char m;//f表示a++，r表示++a,x表示没有自加或自减操作
char o;//'-'还是'+'
};
string s,expr,ex;
int mark[26];
bool used[26];
int main()
{
ios::sync_with_stdio(false);
while(getline(cin,ex))
{
s.clear();
for(int i=0;i<ex.size();i++)
{
if(ex[i]!=' ')
s+=ex[i];
}
for(int i=0;i<26;i++)
mark[i]=i+1;
memset(used,false,sizeof(used));
expr.clear();//expr为去掉自加自减运算符后的表达式
queue<node> q;//队列中保存每个变量是自加、自减还是没有运算符
for(int i=0;i<s.size();)
{
if(s[i]>='a'&&s[i]<='z')
{
used[s[i]-'a']=true;
if(i==0)
{
if(i+1>=s.size())//防止expr="a"
{
expr+=s[i];
q.push(node{'x','x'});
break;
}
if(s[i+1]==s[i+2])
{
q.push(node{'f',s[i+1]});
expr+=s[i];
if(i+3<s.size())
{
expr+=s[i+3];
i+=3;
}
else
i+=2;
}
else
{
q.push(node{'x','x'});
expr+=s[i];
expr+=s[i+1];
i+=1;
}
}
else
{
if(s[i-1]==s[i-2])
{
q.push(node{'r',s[i-1]});
expr+=s[i];
if(i+1<s.size())
expr+=s[i+1];
i+=1;
}
else
{
if(i+2<s.size())
{
if(s[i+1]==s[i+2])
{
q.push(node{'f',s[i+1]});
expr+=s[i];
if(i+3<s.size())
{
expr+=s[i+3];
i+=3;
}
else
i+=2;
}
else
{
q.push(node{'x','x'});
expr+=s[i];
expr+=s[i+1];
i+=1;
}
}
else
{
q.push(node{'x','x'});
expr+=s[i];
if(i+1<s.size())
expr+=s[i+1];
i++;
}
}
}
}
else
i++;
}
int ans=0;
for(int i=0;i<expr.size();)
{
if(i==0)
{
node t=q.front();
q.pop();
if(t.m=='x')
ans=mark[expr[i]-'a'];
else
{
if(t.m=='f')//a++
{
ans=mark[expr[i]-'a'];
if(t.o=='+')
mark[expr[i]-'a']++;
else
mark[expr[i]-'a']--;
}
else//++a
{
if(t.o=='+')
mark[expr[i]-'a']++;
else
mark[expr[i]-'a']--;
ans=mark[expr[i]-'a'];
}
}
i++;
}
else
{
char o=expr[i];
char c=expr[i+1];
node t=q.front();
q.pop();
if(o=='-')
{
if(t.m=='f')//a++
{
ans-=mark[c-'a'];
if(t.o=='+')
mark[c-'a']++;
else
mark[c-'a']--;
}
else//++a
{
if(t.m=='x')
ans-=mark[c-'a'];
else
{
if(t.o=='+')
mark[c-'a']++;
else
mark[c-'a']--;
ans-=mark[c-'a'];
}
}
}
else
{
if(t.m=='f')//a++
{
ans+=mark[c-'a'];
if(t.o=='+')
mark[c-'a']++;
else
mark[c-'a']--;
}
else//++a
{
if(t.m=='x')
ans+=mark[c-'a'];
else
{
if(t.o=='+')
mark[c-'a']++;
else
mark[c-'a']--;
ans+=mark[c-'a'];
}
}
}
i+=2;
}
}
cout<<"Expression: "<<ex<<endl;
cout<<" value = "<<ans<<endl;
for(int i=0;i<26;i++)
{
if(used[i])
cout<<" "<<(char)('a'+i)<<" = "<<mark[i]<<endl;
}
}
return 0;
}
解答：
小白书上的练习题，题目上标着是二叉树，可是我没看出来-_-||| 直接用字符串处理给解决了，感觉应该是使用表达式树来处理双目运算符吧。
思路很简单，首先遍历表达式，判断表达式中每个变量前面两个运算符和后面两个运算符当中是否有相等的符号，如果包含相等的符号，那么说明该变量有自加自减的运算符，将该变量的自操作算符所在变量的前面或是后面，以及是加法还是减法保存在队列当中，同时在原表达式中去掉，仅保留双目运算符，并存储在expr当中。
使用mark来标记每个变量的当前值，遍历expr中的每个变量，根据队列中的信息，计算表达式值即可。
上一篇： 旗舰屏幕体验越来越好 高通公司功不可没：可惜被忽略了
下一篇： 2020.7.21集训