我在寻找用波兰语前缀表示法计算表达式的递归解决方案,没有找到,但我找到了伪代码,我想把它翻译成C++,但很难。我写了一些我不知道该怎么做的大字母。请纠正我,我是java爱好者,对我来说C++一团糟,但无能为力。
int preEval(stack<string> stos){
string el = "";
if(stos.empty()){
return 0;
}else if(stos.top() IS VALUE){
string el = stos.top();
stos.pop();
return atoi(el.c_str());
}else if(stos.top() IS OPERATOR){
int x = preEval(stos);
int y = preEval(stos);
return x OPERATOR y;
}
return 0;
}
编辑
当我有像/10 5这样的表达式时,堆栈应该假设有元素(从顶部)/10 5还是5 10/?只是问,因为如果我想在/10 5中,我必须以某种方式向后读字符串。
我认为,更好的解决方案是将工作分为两个阶段:词法分析和解析。
在词法分析阶段,您对每个标记进行分类,以查看它是运算符(+
、-
等)还是常量,或者可能是变量。然后将解析后的实体打包到一个包含类型和附加信息的结构中。
在代码提供的解析阶段,您不使用字符串,而是使用结构。看看这个结构,你就能很容易地找到它的类型。(如果您选择构建从公共基础派生的结构层次结构,它可以是结构内部的字段,也可以是结构的类型。)
实际上,Java和C++中的逻辑应该是相同的。
如果你有这样的函数:
#include <assert.h>
#include <errno.h>
#include <stdlib.h>
#include <iostream>
#include <stack>
#include <string>
using std::stack;
using std::string;
using std::cerr;
enum Operator {
operator_none,
operator_plus,
operator_minus
};
Operator tokenOperator(const string &token)
{
if (token=="+") return operator_plus;
if (token=="-") return operator_minus;
return operator_none;
}
int applyOperator(Operator op,int x,int y)
{
switch (op) {
case operator_plus: return x+y;
case operator_minus: return x-y;
case operator_none:
break;
}
assert(false);
return 0;
}
bool isValue(const string &token,int &output_value)
{
char *end = 0;
errno=0;
output_value = strtol(token.c_str(),&end,10);
if (errno!=0) return false;
return *end==' ';
}
bool isOperator(const string &token,Operator &output_operator)
{
output_operator = tokenOperator(token);
return output_operator!=operator_none;
}
然后preEval可以这样实现:
int preEval(stack<string> &stos)
{
if (stos.empty()) return 0;
string el = stos.top();
stos.pop();
int value = 0;
Operator op = operator_none;
if (isValue(el,value)) return value;
if (isOperator(el,op)) {
int x = preEval(stos);
int y = preEval(stos);
return applyOperator(op,x,y);
}
return 0;
}
#include <string>
#include <map>
using namespace std;
bool is_value(string s) {
return s.find_first_not_of("0123456789") == string::npos;
}
int do_add(int x, int y) {
return x + y;
}
int do_subtract(int x, int y) {
return x - y;
}
// etc.
typedef int (*binary_op)(int, int); // Give this function pointer type a nice name
map<string, binary_op> ops;
// Somewhere before the preEval() is ever called
ops["+"] = do_add;
ops["-"] = do_subtract; // etc.
binary_op lookup_op(string s) {
map<string, binary_op>::const_iterator it = ops.find(s);
if (it != ops.end()) {
return *it;
} else {
return NULL;
}
}
现在,不用单独测试令牌是否是运算符,然后再执行该运算符,而是使用单个函数调用来获取指向需要调用的运算符函数的指针(如果令牌是运算符),否则为NULL。即:
}else if(stos.top() IS OPERATOR){
int x = preEval(stos);
int y = preEval(stos);
return x OPERATOR y;
}
成为
} else {
binary_op op = lookup_op(stos.top());
if (binary_op != NULL) {
stos.pop(); // This fixes the bug I mentioned in my top comment
int x = preEval(stos);
int y = preEval(stos);
return op(x, y);
} else {
syntax_error();
}
}