2019独角兽企业重金招聘Python工程师标准>>>
题意:
C 表达式运算, 变量为 a-z, 代表运算数为 1-26; 运算符包括 +, -, ++, --; 要求输出原表达式的运算结果, 及运算完后各个变量的值.
1. 每个变量只会出现一次;
2. 不会出现 a+++b 这样带歧义的表达式;
3. ++ 或 -- 不会既出现在变量前面, 又出现在后面.
思路:
1. 把空格去掉;
2. 把 ++ 与 -- 去掉, 把相应的变量按先缀/后缀计算完替换成数字;
(1). 从字符串起始开始, 每次往后数2位, 看这三位是否满足 a++, a--, ++a, --a 这样的形式, 若满足, 则这是一个前缀/后缀表达式的变量;
3. 在进行 2 的时候, 把碰到的每个变量的值都记录下来(用 map), 如果有前缀/后缀运算, 就把运算完后变量的结果记录下来;
4. 每碰到一个运算符, 接下来一定是一个变量, 此时, 只需根据运算符 +, - , 把当前变量与前面的计算结果进行运算即可.
要点:
map 的 key 默认就是字典序的, 所以输出时, 直接用 iterator 进行 ++ 输出即可.
题目:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=263
代码:
# include <iostream>
# include <string>
# include <cstdio>
# include <cstring>
# include <vector>
# include <algorithm>
# include <cctype>
# include <iterator>
# include <assert.h>
# include <map>
using namespace std;typedef map<char, int>::iterator MIT;// 本运算式中使用的变量
map<char, int> usedVariables;
map<char, int> variables;// 初始化 a-z 为 1-26
void initVariables(map<char, int>& variables) {for (int i=0; i<26; i++) {variables['a' + i] = i + 1;}
}// 去除空格
string removeSpace(const string& line) {string result;for (int i=0; i<line.size(); i++) {if (!isspace(line[i])) result += line[i];}return result;
}// 判断从 index 往后 3 位是否为 ++a 格式
bool isPrefixAdd(const string& expression, int index) {return expression[index] == '+' &&expression[index+1] == '+' && islower(expression[index+2]);
}// 判断从 index 往后 3 位是否为 --a 格式
bool isPrefixMinus(const string& expression, int index) {return expression[index] == '-' &&expression[index+1] == '-' && islower(expression[index+2]);
}// 判断从 index 往后 3 位是否为 a++ 格式
bool isPostfixAdd(const string& expression, int index) {return islower(expression[index]) &&expression[index+1] == '+' && expression[index+2] == '+';
}// 判断从 index 往后 3 位是否为 a-- 格式
bool isPostfixMinus(const string& expression, int index) {return islower(expression[index]) &&expression[index+1] == '-' && expression[index+2] == '-';
}// 获取 expression[index] 处的变量值, 若是正常变量, 则index 前进 1
// 若取到一个 ++ 或 -- , 则 index 前进 3
// 并把变量的值存放到 usedVariables 中
// 返回值: first 为变量值, second 为下一步操作的 index
pair<int, int> getVariable(const string& expression, int index) {int value;char c;if (isPrefixAdd(expression, index)) { // ++aindex = index+2;c = expression[index];value = variables[c] + 1;usedVariables[c] = value;} else if (isPrefixMinus(expression, index)) { // --aindex = index+2;c = expression[index];value = variables[c] - 1;usedVariables[c] = value;}else if (isPostfixAdd(expression, index)) { // a++c = expression[index];index = index+2;value = variables[c];usedVariables[c] = value + 1;}else if (isPostfixMinus(expression, index)) { // a--c = expression[index];index = index+2;value = variables[c];usedVariables[c] = value - 1;} else { // aassert(islower(expression[index]));c = expression[index];value = variables[c];usedVariables[c] = value;}return make_pair(value, ++index);
}// 计算表达式
int calcExpression(const string& expression) {int i = 0;pair<int, int> variable;// 取第一个变量variable = getVariable(expression, i);int value = variable.first;i = variable.second;// 如果到结尾了, 说明这里只有一个变量if (i >= expression.size()) return value;while (i < expression.size()) {// 取运算符char op = expression[i];++i;// 取接下来的变量, 有运算符就必定有变量variable = getVariable(expression, i);int next = variable.first;i = variable.second;// 计算if (op == '+') {value += next;} else { // op == '-'value -= next;}}return value;
}int main(int argc, char const *argv[])
{#ifndef ONLINE_JUDGEfreopen("327_i.txt", "r", stdin); freopen("uva_o.txt", "w", stdout); #endifinitVariables(variables);string line;while (getline(cin, line)) {usedVariables.clear();string expression = removeSpace(line);int value = calcExpression(expression);// 输出printf("Expression: %s\n", line.c_str());printf(" value = %d\n", value);for (MIT it = usedVariables.begin(); it != usedVariables.end(); it++) {printf(" %c = %d\n", it->first, it->second);}}return 0;
}
环境: C++ 4.5.3 - GNU C++ Compiler with options: -lm -lcrypt -O2 -pipe -DONLINE_JUDGE