表达式求值 turboc 2
1.一个语义分析程序，大家受编译原理这本书的毒害，使用栈的思想，其实完全就是不科学的。
2.数学运算是有优先级的，完全可以参考完全二叉树的模型来构建。
3.以下代码，仅供学习交流使用，出现问题，本人概不负责。
/****算术表达式的分析和计算，文件名：Test.cpp，代码/注释：sa****
***** 在VC6,VS2008和Dev-C下调试通过 ****/
#include
#include
#include
#include
#include
#define EXP_LEN 100 //定义输入字符缓冲区的长度
/*------------出错代码的宏定义--------------*/
#define INVALID_CHAR_TAIL 0 //表达式后跟有非法字符
#define CHAR_AFTER_RIGHT 1 //右括号后连接非法字符
#define LEFT_AFTER_NUM 2 //数字后非法直接连接左括号
#define INVALID_CHAR_IN 3 //表达式中含有非法字符
#define NO_RIGHT 4 //缺少右括号
#define EMPTY_BRACKET 5 //括号内无表达式
#define UNEXPECTED_END 6 //预期外的算术表达式结束
using namespace std;
const string ErrCodeStr[]= //表达式出错信息
{
"表达式后跟有非法字符！",
"右括号后连接非法字符！",
"数字后非法直接连接左括号！",
"表达式中含有非法字符！",
"缺少右括号！",
"括号内无表达式或表达式不完整！",
"表达式非法结束或表达式不完整！"
};
static char expr[EXP_LEN]; //算术表达式输入字符缓冲区
static int pos; //字符指示器标志：用来保存正在分析的字符的位置
static jmp_buf errjb; //出错跳转缓冲器
//********以下是函数声明*********
int E_AddSub(); //产生式"E -> T+E | T-E | T"的函数，用来分析加减算术表达式。
int T_MulDiv(); //产生式"T -> F*T | F/T | F"的函数，用来分析乘除算术表达式。
int F_Number();//产生式"F -> i | (E)"的函数，用来分析数字和括号内的表达式。
void Error(int ErrCode);//出错处理函数，可以指出错误位置，出错信息。
//主
int main()
{
int ans; //保存算术表达式的计算结果
bool quit=false; //是否退出计算
do
{
//在此设定一个跳转目标，如果本程序的其他函数调用longjmp，
//执行指令就跳转到这里，从这里继续执行。
if(setjmp(errjb)==0) //如果没有错误
{
pos=0; //初始化字符指示器为0，即指向输入字符串的第一个字符。
cout<<"请输入一个算术表达式（输入“Q”或“q”退出）："<<endl;
cin>>expr; //输入表达式，填充表达式字符缓冲区。
if(expr[0]=='q'||expr[0]=='Q')
//检查第一个字符，是否退出？
quit=true;
else
{
//调用推导式"E -> T+E | T-E | T"的函数，
//从起始符号"E"开始推导。
ans=E_AddSub();
//此时，程序认为对表达式的语法分析已经完毕，下面判断出错的原因：
//如果表达式中的某个右括号后直接跟着数字或其他字符，
//则报错，因为数字i不属于FOLLOW(）)集。
if(expr[pos-1]==')'&&expr[pos]!='\0')
Error(CHAR_AFTER_RIGHT);
//如果表达式中的某个数字或右括号后直接跟着左括号，
//则报错，因为左括号不属于FOLLOW(E)集。
if(expr[pos]=='(')
Error(LEFT_AFTER_NUM);
//如果结尾有其他非法字符
if(expr[pos]!='\0')
Error(INVALID_CHAR_TAIL);
cout<<"计算得出表达式的值为："<<ans<<endl;
}
}
else
{
//setjmp(errjb)!=0的情况：
cout<<"请重新输入!"<<endl;
}
}
while(!quit);
return 0;
}
//产生式"E -> T+E | T-E | T"的函数，用来分析加减算术表达式。
//返回计算结果
int E_AddSub()
{
int rtn=T_MulDiv(); //计算加减算术表达式的左元
while(expr[pos]=='+'||expr[pos]=='-')
{
int op=expr[pos++]; //取字符缓冲区中当前位置的符号到op
int opr2=T_MulDiv(); //计算加减算术表达式的右元
//计算求值
if(op=='+') //如果是"+"号
rtn+=opr2; //则用加法计算
else //否则（是"-"号）
rtn-=opr2; //用减法计算
}
return rtn;
}
//推导式"T -> F*T | F/T | F"的函数，用来分析乘除算术表达式。
//返回计算结果
int T_MulDiv()
{
int rtn=F_Number(); //计算乘除算术表达式的左元
while(expr[pos]=='*'||expr[pos]=='/')
{
int op=expr[pos++]; //取字符缓冲区中当前位置的符号到op
int opr2=F_Number(); //计算乘除算术表达式的右元
//计算求值
if(op=='*') //如果是"*"号
rtn*=opr2; //则用乘法计算
else //否则（是"\"号）
rtn/=opr2; //用除法计算
}
return rtn;
}
//产生式"F -> i | (E)"的函数，用来分析数字和括号内的表达式。
int F_Number()
{
int rtn; //声明存储返回值的变量
//用产生式F->(E)推导：
if(expr[pos]=='(') //如果字符缓冲区当前位置的符号是"("
{
pos++; //则指示器加一指向下一个符号
rtn=E_AddSub(); //调用产生式"E -> T+E | T-E | T"的分析函数
if(expr[pos++]!=')') //如果没有与"("匹配的")"
Error(NO_RIGHT); //则产生错误
return rtn;
}
if(isdigit(expr[pos])) //如果字符缓冲区中当前位置的字符为数字
{
//则用产生式F -> i推导
//把字符缓冲区中当前位置的字符串转换为整数
rtn=atoi(expr+pos);
//改变指示器的值，跳过字符缓冲区的数字部分，找到下一个输入字符。
while(isdigit(expr[pos]))
pos++;
}
else //如果不是数字则产生相应的错误
{
if(expr[pos]==')') //如果发现一个")"
Error(EMPTY_BRACKET); //则是括号是空的，即括号内无算术表达式。
else if(expr[pos]=='\0') //如果此时输入串结束
Error(UNEXPECTED_END); //则算术表达式非法结束
else
Error(INVALID_CHAR_IN); //否则输入字符串中含有非法字符
}
return rtn;
}
//出错处理函数，输入错误代码，可以指出错误位置，出错信息。
void Error(int ErrCode)
{
cout<<''; //换行
while(pos--)
cout<<' '; //打印空格，把指示错误的"^"移到输入字符串的出错位置
cout<<"^ 语法错误 ！！！ "
<<ErrCodeStr[ErrCode] //输出错误信息
<<endl<<'\a';
longjmp(errjb,1); //跳转到main()函数中的setjmp调用处，并设置setjmp(errjb)的返回值为1
}
本人写了好久，呵呵，你好轻松啊！唉，学编程要多练，
http://tieba.baidu.com/club/10868002/invite/join/?c=13081498409fa3da8e93c56cd1b57926109
进我的贴吧俱乐部看看吧
#include<stdlib.h>
#include<stdio.h>
#define OK 0
#define ERROR -1
typedef char element;
typedef struct SNode
{
element data;
struct SNode *next;
}SNode,*LinkStack;
void Create_linkStack(LinkStack &L)
{
L=(LinkStack)malloc(sizeof(SNode));
if(!L)
printf("申请失败!\n");
L->next=NULL;
}
int Push(LinkStack &top,element e)
{
SNode *q;
q=(LinkStack)malloc(sizeof(SNode));
if(!q)
{
printf("溢出!\n");
return ERROR;
}
q->data=e;
q->next=top->next;
top->next=q;
return OK;
}
char Pop(LinkStack &top,element &e)
{
SNode *q;
if(!top)
{
printf("错误!");
return ERROR;
}
e=top->next->data;
q=top->next;
top->next=q->next;
free(q);
return e;
}
char GetTop(LinkStack &top)
{ element e;
e=top->next->data;
return e;
}
int In(char c)
{
int i;
int flag=1;
char OP[]={"+-*/()#"};
for(i=0;i<7;i++)
{ if(c==OP[i])
flag=0;
}
return flag;
}
int contrast(char ch)
{
switch(ch)
{
case '+': return 0;break;
case '-': return 1;break;
case '*': return 2;break;
case '/': return 3;break;
case '(': return 4;break;
case ')': return 5;break;
case '#': return 6;break;
default : return -1;
}
}
int PriorTable(int m,int n)
{
int a[7][7];
int i,j;
for(i=0;i<7;i++)
{
for(j=0;j<7;j++)
a[i][j]=1;
}
a[6][6]=a[4][5]=0;
for(j=0;j<5;j++)
{
a[6][j]=-1;
a[4][j]=-1;
}
a[0][2]=a[0][3]=a[0][4]=-1;
a[1][2]=a[1][3]=a[1][4]=-1;
a[2][4]=-1;
a[3][4]=-1;
return a[m][n];
}
char Compare(char opr,char c)
{
int m,n;
char tag;
m=contrast(opr);
n=contrast(c);
if(PriorTable(m,n)==1)
tag='>';
if(PriorTable(m,n)==0)
tag='=';
if(PriorTable(m,n)==-1)
tag='<';
return tag;
}
char Operate(char a,char theta,char b)
{
int t=0;
switch(theta)
{
case '+': t=(a-'0')+(b-'0');break;
case '-': t=(a-'0')-(b-'0');break;
case '*': t=(a-'0')*(b-'0');break;
case '/': t=(a-'0')/(b-'0');break;
default : printf("错误。\n");
}
return (t+'0');
}
char EvaluateExpression()
{
char c;
char theta;
char a=0,b=0;
LinkStack OPTR;
LinkStack OPND;
Create_linkStack(OPTR);
Push(OPTR,'#');
Create_linkStack(OPND);
printf("请输入表达式:\n");
c=getchar();
while(c!='#'||GetTop(OPTR)!='#')
{
int temp;
temp=In(c);
if(temp)
{
Push(OPND,c);
c=getchar();
}
else
{
switch(Compare(GetTop(OPTR),c))
{
case '<':
Push(OPTR,c);
c=getchar();
break;
case '=':
Pop(OPTR,c);
c=getchar();
break;
case '>':
{
theta=GetTop(OPTR);
Pop(OPTR,theta);
Pop(OPND,b);
Pop(OPND,a);
Push(OPND,Operate(a,theta,b));
break;
}
}
}
}
return GetTop(OPND);
}
void main()
{
printf("%c\n",EvaluateExpression());
}
//VC下的 有+-*/^浮点数运算
#include <stdio.h>
#include <math.h>
#include <stack>
#define isdigit(a) (a>='0'&&a<='9')?true:false
char str[100];
int len;
const char A[10][10]={
"?+-*/^()#",
"+>><<<<>>",
"->><<<<>>",
"*>>>><<>>",
"/>>>><<>>",
"^>>>>><>>",
"(<<<<<<=?",
")>>>>>?>>",
"#<<<<<<?="
};
double gainNum()
{
double re=0,i;
bool iszheng=true;
if(str[len]=='-')
{
iszheng=false;
len++;
}
while(isdigit(str[len]))
{
re=re*10+str[len]-'0';
len++;
}
if(str[len]=='.')
{
i=0.1;
len++;
while(isdigit(str[len]))
{
re=re+(str[len]-'0')*i;
len++;
i/=10;
}
}
if(iszheng)
return re;
return -re;
}
double operate(double a,double b,char theta)
{
switch(theta)
{
case '+':
return a+b;
case '-':
return a-b;
case '*':
return a*b;
case '/':
return a/b;
case '^':
return pow(a,b);
}
}
char compare(char op1,char op2)
{
int i=0,j=0;
while(A[i][0]!=op1)i++;
while(A[0][j]!=op2)j++;
return A[i][j];
}
main()
{
std::stack<double> NUM;
std::stack<char> OP;
char ch,theta;
double a,b;
while(gets(str))
{
len=0;
str[strlen(str)+1]='\0';
str[strlen(str)]='#';
OP.push('#');
ch=str[len];
while(ch!='#'||OP.top()!='#')
{
if(isdigit(ch)||ch=='-'&&(len==0||!isdigit(str[len-1])))
{
NUM.push(gainNum());
ch=str[len];
}
else
{
theta=OP.top();
switch(compare(theta,ch))
{
case '>':
OP.pop();
a=NUM.top();
NUM.pop();
b=NUM.top();
NUM.pop();
NUM.push(operate(b,a,theta));
break;
case '<':
OP.push(ch);
ch=str[++len];
break;
case '=':
OP.pop();
ch=str[++len];
break;
}
}
}
printf("%lf\n",NUM.top());
NUM.pop();
OP.pop();
}
}
不懂你表达的意思
在解说清楚点了
