中缀表达式,波兰式与逆波兰式
中缀表达式
我们通常见到的算术表达式就是中缀表达式,如 1+2x3+(4x5-6)x7。中缀表达式可以以树的形式表示为:
波兰式
中缀表达式比较直观,但对计算机来说比较难用于计算。因此在 1920 年,由波兰科学家扬.武卡谢维奇提出了一种不需要括号的计算表达式的方法,将操作符写到操作数之前,称做前缀表达式,又叫波兰式。
如上述算式 1+2*3+(4*5-6)*7
写为波兰式为:++1*23*-*4567
。
在计算时,从左到右扫描算式,每遇到相邻两个操作数,则将其与前面的操作符进行计算,用结果替换原来的操作符和操作数,直到计算结束。
如:
++1*23*-*4567
===>++16*-*4567
===>+7*-*4567
===>+7*-'20'67
===>+7*'14'7
===>+7'98'
===>105
逆波兰式
逆波兰式是是另一种计算表达式的方法,它与波兰式相反,将操作符写到操作数之后,也称作后缀表达式。
如上述算式 1+2*3+(4*5-6)*7
写为逆波兰式为:123*+45*6-7*+
。
逆波兰式可以使用栈来求值,从左到右扫描表达式,每遇到一个操作数则将其入栈,当遇到一个操作符时,将栈顶的两个操作数弹出,并计算结果,然后将结果入栈。当扫描结束时,栈顶元素就是表达式计算结果。
逆波兰式计算图示
逆波兰式求值代码实现
我们使用之前讲到的抽象数据类型(ADT)-栈栈代码来实现此功能。
#define NOTATION_MAX (256)
int calcNotationValue(const char* RPNotation)
{
ttStack* stack = stackInit();
for (int i = 0; i < strlen(RPNotation); i++) {
if (isdigit(RPNotation[i]))
push(stack, RPNotation[i] - '0');
else {
int value1 = pop(stack);
int value2 = pop(stack);
if (RPNotation[i] == '*')
value2 *= value1;
else if (RPNotation[i] == '/')
value2 /= value1;
else if (RPNotation[i] == '+')
value2 += value1;
else
value2 -= value1;
push(stack, value2);
}
}
int total = pop(stack);
stackDestory(stack);
return total;
}
中缀表达式转逆波兰式
中缀表达式转为逆波兰式也可以通过一个栈来实现,先建立一个空栈,然后从左到右扫描原表达式,当遇到一个操作数则直接写入输出表达式,如果遇到一个操作符,如果操作符为左括号“(”,则将左括号入栈,当遇到一个右括号“)”时,从栈中弹出操作符写入输出表达式中,直到弹出左括号为止,左括号不写入表达式。如果是其它操作符,则每次将其与栈顶操作符比较,如果栈顶操作符优先级不低于该操作符,则将栈顶操作符弹出,写入输出表达式,直到栈顶操作符优先级低于该操作符或栈顶为左括号或栈为空为止。
图示
中缀表达式转逆波兰式代码实现
我们同样使用前面讲到的栈来实现此功能。
//infix expression to reverse polish notation
void infixToReversePolish(char* notation)
{
char infix[NOTATION_MAX] = { 0 };
strncpy(infix, notation, 255);
infix[255] = 0;
memset(notation, 0, NOTATION_MAX);
int length = 0;
ttStack* stack = stackInit();
for (int i = 0; i < strlen(infix); i++) {
if (isdigit(infix[i]))
notation[length++] = infix[i];
else if (infix[i] == '(')
push(stack, infix[i]);
else if (infix[i] == ')') {
while (!stackEmpty(stack)) {
char op = pop(stack);
if (op == '(')
break;
notation[length++] = op;
}
} else {
while (!stackEmpty(stack)) {
char op = top(stack);
if (op == '(' || higherPrecedenceThan(infix[i], op))
break;
pop(stack);
notation[length++] = op;
}
push(stack, infix[i]);
}
}
while (!stackEmpty(stack))
notation[length++] = pop(stack);
notation[length] = 0;
stackDestory(stack);
}
测试代码:
int main(int argc, char* argv[])
{
char notation[NOTATION_MAX] = { 0 };
snprintf(notation, NOTATION_MAX - 1, "1+2*3+(4*5-6)*7");
infixToReversePolish(notation);
printf("reversePolishNotation:%s\n", notation);
int total = calcNotationValue(notation);
printf("total:%d\n", total);
return 0;
}
参考:
<数据结构与算法分析-C语言实现> P3 数据结构与算法分析-C语言实现>