h*****f
发帖数: 248 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: henrysf (Henry), 信区: JobHunting
标 题: Re: L 电面
发信站: BBS 未名空间站 (Thu Oct 18 01:46:20 2012, 美东)
我写了以下的code, 之后就被拒了, 回信是说别的candidate写得比较好, 我还没看出
问题.
Additional requirements:
- The only operators you need to implement are +, -, *, and /.
However, your implementation should make it relatively easy to
add more operators.
- The calculator should accept floating point numbers and output
floating point numbers (i.e. when the input is 2 3 / the result
is 0.66667).
- The calculator will read a postfix expression contained in a
single line from stdin and output the result to stdout.
- Each line should be considered independently, so results and errors
from the previous invocation do not affect the next invocation.
- After each evaluation, the calculator must prompt for another
expression, continuing until the user enters the text
“exit” (without the quotes).
- The calculator must output an error message if the expression
contains an error. For example, characters like ‘a’ or ‘.’ or
‘~’ will generate error messages. Also, invalid postfix
expressions must generate an error message. For example, the
expression 2 + 3 is not a valid postfix expression.
- When an error is encountered, the program will NOT exit, but
will prompt the user for a new entry.
any feedback about enhancement is more than welcome:
#include
#include
#include
#include
#include
#include
#include
class Calculator {
private:
std::vector::const_reverse_iterator m_citer;
std::vector::const_reverse_iterator m_lastCIter;
const std::vector* m_pTokens;
public:
double run(const std::vector& expressionTokens) {
m_pTokens = &expressionTokens;
m_citer = m_pTokens->rbegin();
m_lastCIter = m_pTokens->rend();
m_lastCIter--;
double result = eval(false);
if (m_lastCIter != m_citer) {
throw std::runtime_error("invalid expression");
}
return result;
}
double eval(bool hasOperator = true) {
if (m_citer == m_pTokens->rend()) {
throw std::runtime_error("invalid expression");
}
const std::string& tmp = *m_citer;
double v;
if (std::stringstream(tmp) >> v) {
if (!hasOperator) {
throw std::runtime_error("invalid expression");
}
return v;
}
// assuming it is an operator first
m_citer++;
double r = eval();
m_citer++;
double l = eval();
if (0 == tmp.compare("+")) {
return r + l;
}
if (0 == tmp.compare("-")) {
return l - r;
}
if (0 == tmp.compare("*")) {
return l * r;
}
if (0 == tmp.compare("/")) {
if (0 == r) throw std::runtime_error("not a number");
return l / r;
}
// no operator
throw std::runtime_error("invalid expression");
}
};
bool processInput(Calculator& c, std::string& input, double& result) {
std::stringstream strstr(input);
std::istream_iterator start(strstr);
std::istream_iterator end;
std::vector results(start, end);
if (results.empty()) {
throw std::runtime_error("empty expression");
}
if (1 == results.size()) {
if (0 == results.at(0).compare("exit")) {
return true;
}
}
result = c.run(results);
return false;
}
void test() {
Calculator c;
{
// test case 1
std::string l("3 + 5");
bool exit = false;
bool hasException = false;
double r = 0;
try {
exit = processInput(c, l, r);
} catch (...) {
hasException = true;
}
assert(exit == false);
assert(hasException);
}
{
// test case 2: basic +
std::string l("3 5 +");
bool exit = false;
bool hasException = false;
double r = 0;
try {
exit = processInput(c, l, r);
} catch (...) {
hasException = true;
}
assert(exit == false);
assert(!hasException);
assert(r == 8.0);
}
{
// test case 3: test extra number
std::string l("3 5 4 +");
bool exit = false;
bool hasException = false;
double r = 0;
try {
exit = processInput(c, l, r);
} catch (...) {
hasException = true;
}
assert(exit == false);
assert(hasException);
}
{
// test case 4: basic /
std::string l("3 5 /");
bool exit = false;
bool hasException = false;
double r = 0;
try {
exit = processInput(c, l, r);
} catch (...) {
hasException = true;
}
assert(exit == false);
assert(!hasException);
assert(r == 0.6);
}
{
// test case 5: basic -
std::string l("3 5 -");
bool exit = false;
bool hasException = false;
double r = 0;
try {
exit = processInput(c, l, r);
} catch (...) {
hasException = true;
}
assert(exit == false);
assert(!hasException);
assert(r == -2);
}
{
// test case 6: test compound
std::string l("3 4 5 * -");
bool exit = false;
bool hasException = false;
double r = 0;
try {
exit = processInput(c, l, r);
} catch (...) {
hasException = true;
}
assert(exit == false);
assert(!hasException);
assert(r == -17);
}
{
// test case 7: test compound
std::string l("+ +");
bool exit = false;
bool hasException = false;
double r = 0;
try {
exit = processInput(c, l, r);
} catch (...) {
hasException = true;
}
assert(exit == false);
assert(hasException);
}
{
// test case 8: test exit
std::string l("exit");
bool exit = false;
bool hasException = false;
double r = 0;
try {
exit = processInput(c, l, r);
} catch (...) {
hasException = true;
}
assert(exit == true);
assert(!hasException);
}
{
// test case 9: x / 0
std::string l("3 0 /");
bool exit = false;
bool hasException = false;
double r = 0;
try {
exit = processInput(c, l, r);
} catch (...) {
hasException = true;
}
assert(exit == false);
assert(hasException);
}
}
int main(int argc, char** argv) {
Calculator c;
std::string line;
#ifndef N_DEBUG
test();
#endif
bool exit = false;
do {
std::cout << "Please enter expression" << std::endl;
getline(std::cin, line, '\n');
double r = 0;
try {
if (!(exit = processInput(c, line, r)))
std::cout << r << std::endl;
} catch (...) {
std::cerr << "Incorrect expression" << std::endl;
}
} while (!exit);
return 0;
} | h*****f
发帖数: 248 | | t****t
发帖数: 6806 | 3 问题是没什么大问题, 不过这种问题经典的做法是弄一个栈shift/reduce, 你非要用递
归当然不能说错, 但是给人感觉肯定不舒服, 而且你还弄个persistent指针across
recursion, 更让人不爽了.
【在 h*****f 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: henrysf (Henry), 信区: JobHunting
: 标 题: Re: L 电面
: 发信站: BBS 未名空间站 (Thu Oct 18 01:46:20 2012, 美东)
: 我写了以下的code, 之后就被拒了, 回信是说别的candidate写得比较好, 我还没看出
: 问题.
: Additional requirements:
: - The only operators you need to implement are +, -, *, and /.
: However, your implementation should make it relatively easy to
: add more operators.
| h*****f
发帖数: 248 | 4 Arrgghh!
Gotchu!
Just that recursion was very obvious to me at that moment. Using the stack
to hold and then pop last 2 as soon as reading an operator just wasn't so
intuitive to me.
Guess that I should not only practice more but also come up with different
solutions for each question.
Thanks! | f*****e
发帖数: 2992 | 5 编译原理经典啊，shift reduce parsing就是那么干的。
stack
【在 h*****f 的大作中提到】
: Arrgghh!
: Gotchu!
: Just that recursion was very obvious to me at that moment. Using the stack
: to hold and then pop last 2 as soon as reading an operator just wasn't so
: intuitive to me.
: Guess that I should not only practice more but also come up with different
: solutions for each question.
: Thanks!
| a*w
发帖数: 4495 | 6 K&R上也有这个例子。
两本书的作者 Aho 和 Kernighan 当时都在 Bell Labs 工作。
【在 f*****e 的大作中提到】
: 编译原理经典啊，shift reduce parsing就是那么干的。
:
: stack
| t****t
发帖数: 6806 | 7 不是practice more或者come up with different solution, 而是这种经典问题是有成
熟解的, 并且例子随处可见. 比如说编译原理课, 比如说yacc parser, 比如说x87的寄
存器模型, 都是shift/reduce的例子. 不能立刻就得到出题人想要的解, 说明你经验不
够(这些都没接触过), 如此而已.
stack
【在 h*****f 的大作中提到】
: Arrgghh!
: Gotchu!
: Just that recursion was very obvious to me at that moment. Using the stack
: to hold and then pop last 2 as soon as reading an operator just wasn't so
: intuitive to me.
: Guess that I should not only practice more but also come up with different
: solutions for each question.
: Thanks!
| l*********s
发帖数: 5409 | 8 Would you learn these stuffs from MS CS degree?
【在 t****t 的大作中提到】
: 不是practice more或者come up with different solution, 而是这种经典问题是有成
: 熟解的, 并且例子随处可见. 比如说编译原理课, 比如说yacc parser, 比如说x87的寄
: 存器模型, 都是shift/reduce的例子. 不能立刻就得到出题人想要的解, 说明你经验不
: 够(这些都没接触过), 如此而已.
:
: stack
| X****r
发帖数: 3557 | 9 编译原理是本科的内容，美国这里研究生也有这样的课。
不过我怀疑一般编译原理的课上不会讲这种简单的东西。
【在 l*********s 的大作中提到】
: Would you learn these stuffs from MS CS degree?
| t****t
发帖数: 6806 | 10 编译原理前面的lexical analysis和syntax analysis都是比较简单的内容, 翻翻书就
好了. 我没有CS degree也知道啊, 当然我学得不深, 涉及理论的东西就是大概知道一
下, 但是实用的算法肯定没问题.
【在 l*********s 的大作中提到】
: Would you learn these stuffs from MS CS degree?
| h*****f
发帖数: 248 | 11 In which section?
【在 a*w 的大作中提到】
: K&R上也有这个例子。
: 两本书的作者 Aho 和 Kernighan 当时都在 Bell Labs 工作。
|
|
