中缀表达式是人类易读的表达式，但是计算机不好操作，因为有运算符优先级的问题，转换为后缀表达式（逆波兰式）的过程也是一个处理优先级的过程。优先级问题处理好之后，计算机可以很好的处理计算问题。
以下是我的实现思路，有可能有不合理的地方，仅供参考。
中缀表达式生成
思路
首先，准备两个栈：
一个运算符栈 stack<char> opera_exp; ，一个后缀表达式栈 stack<string> suffix_exp; 。
下一步，从左到右依次遍历传入表达式，
现在我们考虑几种情况：
如果是操作数，直接入表达式栈
suffix_exp;
值得注意的是可能操作数是多位的，我们需要一个缓冲变量来存储每位的字符并拼接起来，在遇到下一个运算符时将拼接的字符入表达式栈。
如果遇到
(，直接入运算符栈。
(的优先级在栈外是最高的，在进入栈后它的优先级将会降到最低。( 只有遇到) 时才会出栈。如果遇到
+、-、*、/、^、%等运算符，则会有优先级的问题，这个时候是栈外优先级的比较，如果遇到的运算符优先级高于运算符栈栈顶运算符，则直接将遇到的运算符入运算符栈，反之则将运算符栈中的元素一一出栈与遇到的运算符比较直到遇到优先级更低的停止（注意这里的优先级是栈内优先级），但有一种特殊情况：当运算符栈栈顶为(时需要特殊处理，由于(在栈外优先级最高，这样会把( 过早的换出来，不符合第二条中的规则。如果遇到
)则将运算符栈中的元素一一出栈直到遇到(停止，注意( 不会入表达式栈，直接丢弃。最后整理：
如果最后为一个操作数，则需要将操作数单独入表达式栈，因为之后不会再遇到运算符，第一步不会再发生。如果运算符栈非空则全部入表达式栈。
具体实现：
设置运算符优先级及比较优先级
//判断运算符优先级, 栈内postion为true反之为false。
static bool PriorCom(char left, char right, bool postion) {
//栈内运算符优先级映射
map<char, short> xinmap = {
{'^', 0b1100},
{'*', 0b0100},
{'/', 0b0100},
{'%', 0b0100},
{'+', 0b0010},
{'-', 0b0010},
{'(', 0b0000},
{')', 0b0001}
};
//栈外运算符优先级映射
map<char, short> xoutmap = {
{'^', 0b1000},
{'*', 0b0100},
{'/', 0b0100},
{'%', 0b0100},
{'+', 0b0010},
{'-', 0b0010},
{'(', 0b1111},
{')', 0b0001}
};
if (postion) {
if (xinmap[left] <= xinmap[right]) {
return true;
}
return false;
}
else {
if (xoutmap[left] > xoutmap[right]) {
return true;
}
return false;
}
}
主体实现：
class Stack_Apply {
public:
static stack<string> PexpreToSexpre(char *exp) {
stack<string> suffix_exp;
stack<char> opera_exp;
//判断表达式括号的合法性
if (!Brack_match(exp)) {
Log::Error("exp is non-conformity!");
}
//缓冲字符，数字可能有多位
string temp = "";
for (size_t i = 0; i < strlen(exp);i++) {
if (isdigit(exp[i]) || exp[i] == '.') {
//拼接字符，如12.4 + 23，12.4有4个字符，需要将字符拼接好后入栈。
temp = temp + exp[i];
//最后的整理
if (i == strlen(exp) - 1 && temp.length() != 0) {
suffix_exp.push(temp);
while (!opera_exp.empty()) {
temp = opera_exp.top();
opera_exp.pop();
suffix_exp.push(temp);
}
temp = "";
}
continue;
}
else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/' || exp[i] == '^' || exp[i] == '%') {
if (temp.length() != 0) {
//将拼接好的字符入栈
suffix_exp.push(temp);
}
//判断运算符的优先级，需要保证运算符栈的栈顶的优先级比较高。
if (opera_exp.empty() || PriorCom(exp[i], opera_exp.top(), false) || (!PriorCom(exp[i], opera_exp.top(), false) && opera_exp.top() == '(')) {
opera_exp.push(exp[i]);
temp = "";
continue;
}
else {
while (!opera_exp.empty() && PriorCom(exp[i], opera_exp.top(), true))
{
temp = opera_exp.top();
suffix_exp.push(temp);
opera_exp.pop();
}
opera_exp.push(exp[i]);
temp = "";
continue;
}
}
else if (exp[i] == '(') {
opera_exp.push(exp[i]);
continue;
}
else if (exp[i] == ')') {
if (temp.length() != 0) {
suffix_exp.push(temp);
}
while (opera_exp.top() != '(') {
temp = opera_exp.top();
opera_exp.pop();
suffix_exp.push(temp);
}
opera_exp.pop();
temp = "";
continue;
}
else {
continue;
}
}
while (!opera_exp.empty())
{
temp = opera_exp.top();
suffix_exp.push(temp);
opera_exp.pop();
}
stack<string> suffix;
while (!suffix_exp.empty()) {
temp = suffix_exp.top();
suffix.push(temp);
suffix_exp.pop();
}
return suffix;
}
}
表达式求值
思路
求值就很简单，准备一个操作数栈，将得到的后缀表达式栈依次出栈，遇到操作数就入操作数栈，遇到运算符就出两次操作数栈，取出两个操作数运行相应的运算，将结果入操作数栈，一直循环，最后操作数栈只有一个元素，就是最后的结果。
实现
class Stack_Apply {
public:
//表达式求值
static stack<long double> ExpressionEvaluation(stack<string> suff_exp) {
stack<long double> operand;
long double left = 0;
long double right = 0;
long double value = 0;
while (!suff_exp.empty())
{
if (suff_exp.top() == "*" || suff_exp.top() == "/" || suff_exp.top() == "^" || suff_exp.top() == "%" || suff_exp.top() == "+" || suff_exp.top() == "-") {
const char* temp = suff_exp.top().data();
right = operand.top();
operand.pop();
left = operand.top();
operand.pop();
switch (temp[0])
{
case '*':
value = left * right;
operand.push(value);
break;
case '/':
value = left / right;
operand.push(value);
break;
case '^':
value = pow(left,right);
operand.push(value);
break;
case '%':
value = fmod(left,right);
operand.push(value);
break;
case '+':
value = left + right;
operand.push(value);
break;
case '-':
value = left - right;
operand.push(value);
break;
default:
Log::Error("exp is non-conformity!");
break;
}
suff_exp.pop();
}
else {
operand.push(std::stold(suff_exp.top()));
suff_exp.pop();
}
}
return operand;
}
};
代码后续再优化吧，现在就这样了。
Top comments (0)