1.为什么要把中缀表达式转化为后缀,前缀?
计算机没法计算带有括号,以及区分优先级的表达式。使用后缀,前缀,消除了括号和优先级。
2、计算机如何计算后缀,前缀表达式?
计算后缀:从左到右遍历后缀表达式,遇到操作数,放进栈,遇到操作符,栈顶两个数出栈,进行运算,运算结果放进栈,直到读完后缀表达式。
计算前缀:从左到右遍历前缀表达式,遇到操作符,放进栈,遇到操作数,查看栈顶,栈顶为操作符,放进栈,栈顶为操作数,取出栈顶操作数和操作符,进行运算,运算后继续判断栈顶的情况。
3、中缀表达式如何转化为后缀,前缀表达式?
转化为后缀:从左到右遍历中缀表达式,遇到操作数,输出,遇到操作符,当前操作符的优先级大于栈顶操作符优先级,进栈,否则,弹出栈顶优先级大于等于当前操作符的操作符,当前操作符进栈。
转化为前缀:从右到左遍历中缀表达式,遇到操作数,输出,遇到操作符,当前操作符的优先级大于等于栈顶操作符优先级,进栈,否则,弹出栈顶优先级大于当前操作符的操作符,当前操作符进栈。
4.优先级:左括号> *,/ > +,- > 右括号
遇到右括号时需要一直弹出栈顶元素直到弹出对应的左括号为止
中缀转化成后缀
map<char,int> mapping;
void initmap()//优先级设置
{
mapping.insert({'+',1});
mapping.insert({'-',1});
mapping.insert({'x',2});
mapping.insert({'/',2});
}
string tohz(string astr)//输入中缀表达式字符串,输出后缀表达式字符串
{
string bstr;
stack<char> st;
for(int i = 0 ; i < astr.size() ; i++)
{
if(isdigit(astr[i])) bstr += astr[i];
else
{
if(st.empty() || mapping[astr[i]] > mapping[st.top()] ) st.push(astr[i]);
else
{
bstr += st.top();
st.pop();
st.push(astr[i]);
}
}
}
while(!st.empty())
{
bstr += st.top();
st.pop();
}
return bstr;
}
后缀表达式算值
void culhz(string astr)//输入后缀表达式字符串,输出int类的值
{
stack<int> st;
for(int i = 0 ; i < astr.size() ; i++)
{
if(isdigit(astr[i]))
{
int num = astr[i]-48;
st.push(num);
}
else
{
int left,right,ans;
right = st.top();st.pop();
left = st.top();st.pop();
if(astr[i] == '+') ans = left+right;
if(astr[i] == '-') ans = left-right;
if(astr[i] == 'x') ans = left*right;
if(astr[i] == '/') ans = left/right;
st.push(ans);
}
}
cout<<st.top()<<endl;
}