中缀表达式转换为后缀表达式并求值c++_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
中缀表达式转换为后缀表达式并求值c++
上传于||文档简介
&&能​提​示​输​入​错​误​信​息​,​能​计​算​包​括​小​数​字​母​等​多​种​运​算
你可能喜欢中缀表达式转后缀表达式并求值_C++_第七城市
中缀表达式转后缀表达式并求值
中缀表达式转后缀表达式并求值，有需要的朋友可以参考下。
RT。题目链接：/index.php?app=problem_title&id=1&problem_id=1743
求一表达式的值。需要注意的有以下几个方面：
1.首先想到的是先将中缀表达式转成后缀表达式，再扫描后缀表达式这一方法。扫描后缀表达式时，每遇到操作数时压栈，遇到操作符时从栈顶弹出2个操作数计算并压栈。最后返回栈顶即为结果。当然，题目中给的是算符优先法规定操作符之间的优先级。也可用其他的方式规定优先级。比如我的方法是事先规定好栈内优先级和栈外优先级。
2.其次，在转化后缀表达式的过程中，最好使用c++的泛型。因为如果用int型的数组来存储后缀式的话，操作符均变成ascii码来存储，有可能与操作数混淆。我的方法是操作符的ascii码减48（即操作符在后缀表达式中以负数形式出现，为了与操作数区分开）后再存储到数组中。另外，如果用char型数组来存后缀式的话，类&#的多位操作数无法支持。
#include&iostream&
#include&cstring&
#define SIZE 100
int main()
int isp[50];
int icp[50];
isp['#'] = 0;
isp['('] = 1;
isp['*']= isp['/'] = 5;
isp['+']= isp['-'] = 3 ;
isp[')'] = 6;
icp['#'] = 0;
icp['('] = 6;
icp['*']= icp['/'] = 4;
icp['+']= icp['-'] = 2 ;
icp[')'] = 1;//规定栈内优先级和栈外优先级
char str[SIZE];//存储输入字符串
int num_stack[SIZE];//计算后缀表达式时使用的栈
char op_stack[SIZE];//中缀表达式转后缀表达式时使用的栈
int i,j,k,
int num[SIZE];
int temp1,temp2;
while(cin&&str)
top_op = -1;
op_stack[++top_op] = '#';//操作符栈
for(i=0; i&strlen(str); i++)
if(str[i] &= '9' && str[i] &= '0')
sum = str[i] - '0';//操作数最高位先赋给sum
while(str[i+1] &= '9' && str[i+1] &= '0')
sum = sum * 10 + (str[i+1] - '0' );
//cout&&&sum=&&&sum&&
//num_stack[++top_num] =//操作数直接进栈
num[j++] =
else//如果是操作符，则弹出栈顶元素比较优先级
//cout&&&top_op=&&&top_op&&
while(top_op & -1)
buf = op_stack[top_op];//返回操作符栈顶并比较
if(isp[buf] & icp[str[i]])
op_stack[++top_op] = str[i];
else if(isp[buf] & icp[str[i]])
num[j++] = op_stack[top_op--] - 48;//退栈并输出操作符
else //相等时直接退栈,也不要忘了break
//扫描后缀表达式并输出
top_num = -1;//初始化数字栈，数字栈现在还没有使用
temp1 = temp2 = 0;
for(k=0; k&j; k++)
if(num[k]!=-1 && num[k]!=-3 && num[k]!=-5 && num[k]!=-6)
num_stack[++top_num] = num[k];//操作数入栈
else if (num[k] == -1)//匹配到除号
temp1 = num_stack[top_num--];
temp2 = num_stack[top_num--];
num_stack[++top_num] = temp2 / temp1;
else if (num[k] == -3)//匹配到减号
temp1 = num_stack[top_num--];
temp2 = num_stack[top_num--];
num_stack[++top_num] = temp2 - temp1;
else if (num[k] == -5)//匹配到加号
temp1 = num_stack[top_num--];
temp2 = num_stack[top_num--];
num_stack[++top_num] = temp2 + temp1;
else if (num[k] == -6)//匹配到乘号
temp1 = num_stack[top_num--];
temp2 = num_stack[top_num--];
num_stack[++top_num] = temp2 * temp1;
cout&&num_stack[top_num];//最后输出当前栈顶即可
最新教程周点击榜
微信扫一扫人人网 - 抱歉
哦，抱歉，好像看不到了
现在你可以:
看看其它好友写了什么
北京千橡网景科技发展有限公司：
文网文[号··京公网安备号·甲测资字
文化部监督电子邮箱：wlwh@··
文明办网文明上网举报电话： 举报邮箱：&&&&&&&&&&&&2312人阅读
简单数据结构的实现（C++）（6）
应杨茜小师妹的请求写了这个程序，找找当年的感觉，呵呵。我把中缀转后缀并求值的代码写成了一个类，注释写的很详细，不多说。首先是类声明：
#ifndef _CALSUFFIX_H_
#define _CALSUFFIX_H_
#include &iostream&
#include &stack&
#include &string&
//中缀转后缀并求值的类
class CalSuffix
//中缀表达式
stack&char& //存取操作符和操作数的栈，用于中缀变后缀
//后缀表达式
stack&bool& //用于存储后缀表达式的中间结果
//计算结果
CalSuffix(); //默认构造函数
CalSuffix(string input); //构造函数
~CalSuffix(); //7构函数
void InfixToSuffix(); //中缀转后缀
void Calculate(); //求后缀表达式的值
string GetSuffix(); //获取后缀表达式
bool GetResult(); //获取计算结果
然后是类定义：
#include &iostream&
#include &stack&
#include &string&
#include &calsuffix.h&
CalSuffix::CalSuffix()
CalSuffix::CalSuffix(string input)
CalSuffix::~CalSuffix()
void CalSuffix::InfixToSuffix()
string::iterator infixI //suffix的迭代器，用于逐个字符扫描suffix
//中缀转后缀
for(infixIter = infix.begin(); infixIter != infix.end(); ++ infixIter)
switch(*infixIter)
//若是V或F，直接放入后缀表达式字符串中
suffix += *infixI
//若是(，压入操作符栈
oper.push('(');
//若是!，压入操作符栈
oper.push('!');
//若是&，且栈顶操作符为!或&，则将栈顶操作符放入后缀表达式并弹栈，然后将&压入操作符栈；否则直接压入
if(!oper.empty() && (oper.top() == '!' || oper.top() == '&'))
suffix += oper.top();
oper.pop();
oper.push('&');
//若是|，且栈顶操作符为!或&或|，则将栈顶操作符放入后缀表达式并弹栈，然后将|压入操作符栈；否则直接压入
if(!oper.empty() && (oper.top() == '!' || oper.top() == '&' || oper.top() == '|'))
suffix += oper.top();
oper.pop();
oper.push('|');
//若是)，则将栈顶操作符放入后缀表达式并弹栈，直至弹出(
while(oper.top() != '(')
suffix += oper.top();
oper.pop();
oper.pop();
//将栈中剩余的操作符全部放入后缀表达式中
while(!oper.empty())
suffix += oper.top();
oper.pop();
void CalSuffix::Calculate()
bool op1, op2; //操作数
string:: //用于遍历suffix的迭代器
//计算后缀表达式的值
for(iter = suffix.begin(); iter != suffix.end(); ++ iter)
switch(*iter)
//若是V，直接压入中间结果栈
intermedia.push(true);
//若是F，直接压入中间结果栈
intermedia.push(false);
//若是!，弹出栈顶元素并做!运算，将结果压回栈中
op1 = intermedia.top();
intermedia.pop();
intermedia.push(!op1);
//若是&，弹出栈顶两个元素并做&运算，将结果压回栈中
op1 = intermedia.top();
intermedia.pop();
op2 = intermedia.top();
intermedia.pop();
intermedia.push(op1 & op2);
//若是|，弹出栈顶两个元素并做|运算，将结果压回栈中
op1 = intermedia.top();
intermedia.pop();
op2 = intermedia.top();
intermedia.pop();
intermedia.push(op1 | op2);
//栈中的最后一个元素就是计算结果
result = intermedia.top();
intermedia.pop();
string CalSuffix::GetSuffix()
bool CalSuffix::GetResult()
测试代码也贴上：
#include &iostream&
#include &string&
#include &calsuffix.h&
int main()
cout && &Input infix expression: & &&
CalSuffix cal(expression);
cal.InfixToSuffix();
cout && &Suffix expression is: \n& && cal.GetSuffix() &&
cal.Calculate();
cout && &The result is: \n& && cal.GetResult() &&
就这样吧！我记得当年我们做课程设计的时候好像也有这么一道题，不过我没选。自己选的什么也记不得了。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：258903次
积分：2082
积分：2082
排名：第14916名
原创：46篇
评论：80条
(2)(1)(1)(1)(4)(1)(2)(2)(1)(3)(1)(2)(2)(1)(1)(2)(2)(3)(1)(3)(12)表达式求值的几种算法 - wjm251 - ITeye技术网站
博客分类：
====== 表达式求值 ======
表达式求值基本有两种算法，算法优先和语法分析
通常我们写的2+3×4叫中缀表达式，算法优先算法很依赖于和中缀表达式等价的后缀表达式，而借助二叉树求值本质也是一样的。
中缀转后缀的基本步骤
有个操作符栈opStack，保留暂时的优先级比较低的操作符，比如3+2*4，当碰到3时就要先入栈
碰到左括号(就一定进opStack，等再碰到左括号)时，将栈中直到左括号为止的所有操作符出栈使用，(使用指的是参与计算或拼二叉树，或拼后缀表达式)
碰到操作符，将栈顶开始往下的所有优先级大于等于本操作符的操作符出栈使用，本操作符入栈。
碰到操作数，直接使用。
贴一下代码先
import java.util.S
public class OperatorPrecedence
* 暂不支持负号，但可以考虑，字符串开头的或操作符后紧挨的或括号后的减号必须算做负号
* @param infixStr
public String infix2sufix(String infixStr){
StringBuilder rst = new StringBuilder();
Stack&Operator& opStack = new Stack&Operator&();
int len = infixStr.length();
for(int i=0;i&i++)
char c = infixStr.charAt(i);
//空格过滤掉
if(c == ' ')
rst.append(" ");
else if(Character.isDigit(c) || c=='.')
rst.append(c);
else if(c == '(')
opStack.push(new Operator('('));
else if(c == ')')
while(opStack.size()&0 && !(opStack.peek().equals(new Operator('('))))
rst.append(" "+opStack.pop().getSymbol());
//将左括号去除
assert opStack.peek().equals(new Operator('('));
opStack.pop();
else if(Operator.operators.contains(String.valueOf(c)))
Operator current = new Operator(c);
//栈空或当前优先级比栈顶的大才入栈,否则，栈内优先级小的挨次出栈拼结果
//pop out all the greater percedence operator
while(opStack.size()&0 && pareTo(opStack.peek())&=0)
rst.append(" "+opStack.pop().getSymbol());
//本操作符入栈
opStack.push(current);
rst.append(" ");
while(opStack.size()&0)
rst.append(" "+opStack.pop().getSymbol());
return rst.toString();
* @param args
public static void main(String[] args)
OperatorPrecedence o = new OperatorPrecedence();
System.out.println(o.infix2sufix("4-(4-3*5+(2*4)+100)/10"));
import java.util.HashM
import java.util.LinkedL
public class Operator implements Comparable
private static HashMap&Operator,Integer& ops = new HashMap&Operator,Integer&();
public static LinkedList&String& operators = new LinkedList&String&();
ops.put(new Operator("("),0);
ops.put(new Operator("+"),1);
ops.put(new Operator("-"),1);
ops.put(new Operator("*"),100);
ops.put(new Operator("/"),100);
for(Operator o : ops.keySet())
operators.add(o.s);
public String getSymbol()
public boolean equals(Object obj)
if(!(obj instanceof Operator))
return this.s.equals(((Operator)obj).s);
public int hashCode()
return this.s.hashCode();
public Operator(String s)
public Operator(char c)
this.s = String.valueOf(c);
public int compareTo(Object o)
return ops.get(this) - ops.get(o);
* @param args
public static void main(String[] args)
System.out.println(ops.get(new Operator("@")));
为避免特殊处理左括号，右括号，以及最后特殊处理操作符栈中的最后剩余操作符。也将他们定义了特定的优先级。
并在栈低放了个优先级很低的特殊的操作符#,初始化一个二维表来存储优先级关系，设定只有栈中（碰到），栈中#碰到#时，优先级为相等，
这时脱去括号。
这样写出的代码更简练一些。
见严蔚敏c语言版《数据结构》，这是偶的大学教程。
2.
其中描述的允许可以拼后缀表达式，
也可以另加一个栈存放操作数，当使用操作数时入栈，当使用操作符时，靠顶两个操作数出栈运算后结果再入栈。这样就直接得到表达式的结果。
如果把其中的运算换成“构建二叉树节点”，这里可以构建出一个表达式的二叉树来（中序遍历就是中缀表达式，后序遍历就是后缀）。
这样可以构建二叉树递归计算二叉树取结果或者直接取表达式的结果
3.
表达式求值的另一种方法，也是最灵活易懂的方式利用编译原理的语法分析。
可以收工根据语法分析来，也可以使用ANTLR这个工具
手工语法分析是要有些编译原理的知识，待续。。
如果用三方工具就简单得多，见另一篇
下载次数: 17
浏览: 72110 次
来自: 沈阳
这个极难重现。。。虽然根据Java(R) Language Spe ...
time.ctime()+8时区时显示'T ...
datetime.strftime(&%H:%M:% ...
今天在邮件列表里头看到有人问碰到这种怎么办s = u'\xbe ...
一定要有自己的鉴别啊}