大家好,又见面了,我是全栈君。
上节我们说到计算机默认的是后缀表达式,那么中缀表达式转后缀表达式的过程就类似于编译过程。
必须得注意这么几个问题:四则运算表达式中的括号必须匹配;根据运算符优先级进行转换;转换后的表达式中没有括号;转换后可以顺序计算出最终结果。
下来我们就讲下具体的转换过程:
1、当前元素 e 为数字:输出
2、当前元素 e 为运算符时:1. 与栈顶运算符进行优先级比较;2.小于等于时将栈顶元素输出,转1;3.大于时将当前元素 e 入栈
3、当前元素 e 为左括号:入栈
4、当前元素 e 为右括号:1.弹出栈顶元素并输出,直至栈顶元素为左括号;2.将栈顶的左括号从栈中弹出
用伪代码描述出来就是这样:
其中的关键点是转换过程中左右括号是重要的标志,那么如何确保表达式中的括号能够左右匹配?
那么在合法的四则运算表达式中:括号必然是成对出现的,左括号必然先于右括号出现,可以用伪代码进行描述:
经过这样,我们就可以确保计算机正确的将中缀表达式转换成后缀表达式,也就是将表达式转换为计算机理解的行为。
那么这是计算机所转换的三个示例:
下来我们构建运行下程序看看输出是否正确执行,我们在构造函数这样输入:
输出结果如下:
匹配函数的具体代码如下:
bool QCalculatorDec::match(QQueue<QString>& exp)
{
bool ret = true;
int len = exp.length();
QStack<QString> stack;
for(int i=0; i<len; i++)
{
if( isLeft(exp[i]) )
{
stack.push(exp[i]);
}
else if( isRight(exp[i]) )
{
if( !stack.isEmpty() && isLeft(stack.top()) )
{
stack.pop();
}
else
{
ret = false;
break;
}
}
}
return ret && stack.isEmpty();
}
转换函数的具体代码如下:
bool QCalculatorDec::transform(QQueue<QString>& exp, QQueue<QString>& output)
{
bool ret = match(exp);
QStack<QString> stack;
output.clear();
while( ret && !exp.isEmpty() )
{
QString e = exp.dequeue();
if( isNumber(e) )
{
output.enqueue(e);
}
else if ( isOperator(e) )
{
while( !stack.isEmpty() && (priority(e) <= priority(stack.top())) )
{
output.enqueue(stack.pop());
}
stack.push(e);
}
else if( isLeft(e) )
{
stack.push(e);
}
else if( isRight(e) )
{
while( !stack.isEmpty() && !isLeft(stack.top()) )
{
output.enqueue(stack.pop());
}
if( !stack.isEmpty() )
{
stack.pop();
}
}
else
{
ret = false;
}
}
while( !stack.isEmpty() )
{
output.enqueue(stack.pop());
}
if( !ret )
{
output.clear();
}
return ret;
}
那么今天的学习就到这了,现在程序已经能按照计算机的思维进行四则运算的读取了,后面我们继续学习相关知识。
转载于:https://blog.51cto.com/12810168/2089623
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107627.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...