把中缀表达式转化为后缀表达式

算法的用途:

我的目的很简单,做一个24点牌的Flash小游戏,接受用户输入的表达式,然后计算结果。貌似在AS中没有可以直接计算字符串表达式的函数,所以只好自己写了。要计算这个表达式(带括号)首先得把括号去掉,括号真的是挺麻烦的一个东东,所以还得选后缀表达式-_-

算法基本思想:

使用三个数组,一个数组保存用户输入的表达式(中缀表达式),一个数组保存后缀表达式,一个数组作为运算符的栈。

从头到尾扫描中缀表达式,对不同类型的字符按不同情况处理;
1、如果是数字则直接放入后缀表达式数组;
2、如果是左括号则直接入栈;
3、如果是右括号,则把从栈顶直到对应左括号之间的运算符依次退栈,并清除对应的左括号;
4、对于运算符,如果该运算符的优先级大于栈顶优先级,则直接入栈,若该运算符的优先级小于等于栈顶优先级,则先把栈顶运算符出栈,写入后缀表达式数组,然后再入栈;
5、扫描完成后,取出栈中所有运算符,写入后缀表达式数组。

示例程序如下(面向过程的C(++)版,在VC6下编译通过):

/****************************/
/* fdream.net */
/* Author:Fdream */
/* 引用此算法请保留此信息 */
/****************************/

#include

const int MAX=40;

void main(void){
char infix[MAX]={‘#’};
char oprator[MAX]={‘@’,’#’};
int opr=1;
char postfix[12]={‘#’};
int post=0;
int i,j,cnt=0,cntl;
char c;

//输入表达式,以等号结束
cin.get(c);
while(c!=’=’){
infix[cnt]=c;
cnt++;
cin.get(c);
}
cntl=cnt;

for(i=0;i switch(infix[i]){
//左括号就直接入栈
case ‘(‘:
cntl=cntl-2;
oprator[opr]=infix[i];
opr++;
break;
//右括号则先退栈,直到遇见第一个左括号
case ‘)’:
for(j=opr-1;j>0;j–){
if(oprator[j]!='(‘){
postfix[post]=oprator[j];
oprator[j]=’#’;
post++;
}
else{
oprator[j] = ‘#’;
break;
}
}
opr=j;
break;
case ‘*’:
case ‘/’:
//如果前一个运算符为*或/,则先退栈,再入栈,否则直接入栈
if (oprator[opr] == ‘*’ || oprator[opr] == ‘/’) {
postfix[post] = oprator[opr];
oprator[opr]=’#’;
post++;
}
oprator[opr] = infix[i];
opr++;
break;
case ‘+’ :
case ‘-‘ :
//如果上一个运算符不是左括号也不是栈顶,则先退栈再入栈
if (oprator[opr-1] != ‘(‘ && oprator[opr-1] != ‘@’) {
postfix[post] = oprator[opr];
oprator[opr]=’#’;
}
oprator[opr] = infix[i];
opr++;
break;
default :
//如果是数字则直接进入后缀表达式数组
postfix[post] = infix[i];
post++;
break;
}
}

//如果扫描完成,则退栈
for(j=opr-1;j>0;j–){
if(oprator[j]!=’@’){
postfix[post]=oprator[j];
oprator[j]=’#’;
}
else
break;
}

//输出结果
for(i=0;i cout << postfix[i];
cout << endl;
}

8 comments on “把中缀表达式转化为后缀表达式”

  1. 这个程序从 运行下什么现象也没有?
    不是说写成拉 function()形式吗?
    怎么还是这样的

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据