80分求解决一个简单的C程序
算术表达式求值（运算数为整数）
运算符为+，-，*，/，（）
一是输入注意算术表达式
二是求表达式的值输出结果
谢谢 高手们!!!!!!!!!!!!
[解决办法]
这可不算太简单，给出一个我的小程序包括4个文件，如下：
//calculator.h
/*==================================================
************简单的表达式求值c++语言的实现**************
==================================================*/
#ifndef _CALCULATOR_H_
#define _CALCULATOR_H_
#include <stdio.h>
#include <ctype.h>
#include <string>
#include <iostream>
using namespace std;
//自定义的堆栈类
#include "stack.h "
struct entry //符号表的表项形式
{
char *lexptr;
int token;
};
class calculate //简单的一遍编译器类的定义
{
public:
calculate():lastchar(-1), lastentry(0),
lineno(1), tokenval(NONE)
{}
~calculate()
{}
public:
void init ();
void parse();
int getResult() //取得最后的计算结果
{
return st_value.top();
}
protected:
//保护成员函数声明
int lookup(char s[]);
int insert(char s[],int tok);
void error(char *m);
void emit(int t, int tval);
int lexan();
private:
//私有成员函数声明
void expr();
void term();
void factor();
void match(int t);
protected:
//类中使用的常量定义
static const int BSIZE=128; //缓冲区大小
static const int NONE=-1;
static const char EOS= '\0 ';
static const int NUM=256;
static const int DIV=257;
static const int MOD=258;
static const int ID=259;
static const int DONE=260;
static const int STRMAX=999; //lexemes数组的大小
static const int SYMMAX=100; //symtable的大小
private:
//私有成员变量声明
char lexemes[STRMAX] ;
int lastchar ; //lexmes的最后引用位置
entry symtable[SYMMAX] ;
int lastentry ;
char lexbuf[BSIZE] ;
int lineno ;
int tokenval ; //与记号关联的属性值
int lookahead ;
//存储表达式每一步的计算值
stack <double> st_value;
};
#endif
//stack.h
/*==========================================================
**********************自定义的堆栈类************************
==========================================================*/
#ifndef _STACK_H_
#define _STACK_H_
#include <deque>
#include <exception>
using namespace std;
template <typename T>
class stack
{
protected:
std::deque <T> c; //存放元素的容器
public:
class ReadEmptyStack:public std::exception
{
public:
virtual const char * what() const throw()
{
return "read empty stack ";
}
};
typename std::deque <T> ::size_type size() const
{
return c.size();
}
bool empty() const
{
return c.empty();
}
void push(const T& elem)
{
c.push_back(elem);
}
T pop()
{
if(c.empty())
{
throw ReadEmptyStack();
}
T elem(c.back());
c.pop_back();
return elem;
}
T& top()
{
if(c.empty())
{
throw ReadEmptyStack();
}
return c.back();
}
};
#endif
[解决办法]
//calculator.cpp
//一遍编译器的实现文件
#include "calculator.h "
//将 DIV,MOD两个记号插入
void calculate::init()
{
entry keywords[] =
{
"div ", DIV,
"mod ", MOD,
0,0
};
entry *p;
for( p = keywords; p-> token; p++)
insert(p-> lexptr,p-> token);
}
//-----------------------------------------------------
//查找标志符函数定义
int calculate::lookup(char s[])
{
int p;
for(p = lastentry; p> 0; p = p-1)
if(strcmp(symtable[p].lexptr, s) == 0)
return p;
return 0;
}
//------------------------------------------------------
//插入标志符函数的定义
int calculate::insert(char s[],int tok)
{
int len;
len = strlen(s); //strlen 计算s的长度
if(lastentry + 1 > = SYMMAX)
error( "lexemes table full ");
if(lastchar + len + 1 > = STRMAX)
error( "lexemes array full ");
lastentry = lastentry + 1;
symtable[lastentry].token = tok;
symtable[lastentry].lexptr = &lexemes[lastchar +1];
lastchar = lastchar + len + 1;
strcpy(symtable[lastentry].lexptr, s);
return lastentry;
}
//------------------------------------------------------
//错误处理函数定义,输出错误显示的字符串
void calculate::error(char *m)
{
fprintf(stderr, "line %d: %s\n ", lineno, m);
return; //非正常终止
}
//-------------------------------------------------------
// 后缀形式的成员函数输出
void calculate::emit(int t, int tval)
{
double lValue, rValue, reValue;
switch(t)
{
case '+ ':
printf( "%c\n ",t);
rValue = st_value.pop();
lValue = st_value.pop();
st_value.push(lValue + rValue);
break;
case '- ':
printf( "%c\n ",t);
rValue = st_value.pop();
lValue = st_value.pop();
st_value.push(lValue - rValue);
break;
case '* ':
printf( "%c\n ",t);
rValue = st_value.pop();
lValue = st_value.pop();
st_value.push(lValue * rValue);
break;
case '/ ':
printf( "%c\n ",t);
rValue = st_value.pop();
lValue = st_value.pop();
st_value.push(lValue / rValue);
break;
case DIV:
printf( "DIV\n ");
rValue = st_value.pop();
lValue = st_value.pop();
st_value.push(lValue / rValue);
break;
case MOD:
printf( "MOD\n ");
rValue = st_value.pop();
lValue = st_value.pop();
st_value.push(lValue * rValue);
break;
case NUM:
printf( "%d\n ",tval);
st_value.push(tval); //压入堆栈
break;
case ID:
printf( "%s\n ",symtable[tval].lexptr);
break;
default:
printf( "token %d,tokenval %d\n ", t, tval);
}
}
//-----------------------------------------------------
//语法分析成员函数定义
int calculate::lexan()
{
int t;
while(1)
{
t = getchar();
if( t== ' ' || t== '\t ')
; //删去空白符
else if(t == '\n ')
lineno = lineno + 1;
else if(isdigit(t))
{
ungetc(t,stdin);
scanf( "%d ",&tokenval);
return NUM;
}
else if(isalpha(t)) //t是字母
{
int p, b = 0;
while(isalnum(t)) //t是字母或数字
{
lexbuf[b] = t;
t = getchar();
b = b + 1;
if (b > = BSIZE)
error( " compiler error ");
}
lexbuf[b] = EOS;
if (t != EOF)
ungetc(t, stdin);
p = lookup(lexbuf);
if (p == 0)
p = insert(lexbuf, ID);
tokenval = p;
return symtable[p].token;
}
else if (t == EOF)
return DONE;
else
{
tokenval = NONE;
return t;
}
}
}
//----------------------------------------------------
void calculate::parse() //分析并翻译表达式列表
{
lookahead = lexan();
while (lookahead != DONE)
{
expr();
cout < <endl < < "the result is: " < <st_value.pop() < <endl;
match( '# ');
}
}
//--------------------
//
void calculate::expr()
{
int t;
term();
while(1)
{
switch(lookahead)
{
case '+ ':
case '- ':
t = lookahead;
match(lookahead);
term();
emit(t,NONE);
continue;
default:
return;
}
}
}
//-----------------------------------------------------
//
void calculate::term()
{
int t;
factor();
while(1)
{
switch(lookahead)
{
case '* ':
case '/ ':
case DIV:
case MOD:
t = lookahead;
match(lookahead);
factor();
emit(t,NONE);
continue;
default:
return;
}
}
}
//-------------------------------------------------------
//
void calculate::factor()
{
switch(lookahead)
{
case '( ':
match( '( ');
expr();
match( ') ');
break;
case NUM:
emit(NUM, tokenval);
match(NUM);
break;
case ID:
emit(ID, tokenval);
match(ID);
break;
default:
error( "systax error ");
}
}
//------------------------------------------------------
//
void calculate::match(int t)
{
if (lookahead == t)
lookahead = lexan();
else
error( "syntax error ");
}
//-------------------------------------------------------
//main.cpp
#include <iostream>
#include "calculator.h "
using namespace std;
int main()
{
cout < < "输入表达式按如下格式：以#号结束 " < <endl;
cout < < " (12+13)-(4*5) # " < <endl;
cout < < "输出后缀表达式， 和最终结果. " < <endl;
calculate object_compile;
object_compile.init();
object_compile.parse();
return 1; //正常终止
}
[解决办法]
mark
这种运算肯定要自定义堆栈的，我曾经也想过实现，但是就是在自定义堆栈的入栈和出栈的这种操作面前停止了。
[解决办法]
看看编译
原理方面书籍
^_^
[解决办法]
没必要上编译原理,数据结构看到栈就够了
一般是两个栈,一个放参数,一个放符号
[解决办法]
#include "stdio.h "
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#include "malloc.h "
#include "string.h "
#include "math.h "
typedef struct
{
char *base;
char *top;
int stacksize;
}SqStack1;
typedef struct
{
double *base;
double *top;
int stacksize;
}SqStack2;
SqStack2 OPND ;SqStack1 OPTR;
int InitStack(SqStack1 &S)
{
S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
if(!S.base)return -2;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 1;
}
int InitStack(SqStack2 &S)
{
S.base=(double *)malloc(STACK_INIT_SIZE*sizeof(double));
if(!S.base)return -2;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 1;
}
double GetTop(SqStack2 S,double e)
{
if(S.top==S.base)return 0;
e=*(S.top-1);
return e;
}
char GetTop(SqStack1 S,char e)
{
if(S.top==S.base)return 0;
e=*(S.top-1);
return e;
}
int Push(SqStack1 &S,char e)
{
if(S.top-S.base> =S.stacksize)
{
S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));
if(!S.base)return -2;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return 1;
}
int Push(SqStack2 &S,double e)
{
if(S.top-S.base> =S.stacksize)
{
S.base=(double *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(double));
if(!S.base)return -2;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return 1;
}
int StackEmpty(SqStack1 S)
{
if(S.base==S.top)
return 1;
else
return 0;
}
int StackEmpty(SqStack2 S)
{
if(S.base==S.top)
return 1;
else
return 0;
}
char Precede(char oper,char c)
{
switch(oper)
{
case '+ ':if(c== '+ '||c== '- '||c== ') '||c== '= ')return '> ';
else return ' < ';
case '- ':if(c== '+ '||c== '- '||c== ') '||c== '= ')return '> ';
else return ' < ';
case '* ':if(c== '( ')return ' < ';
else return '> ';
case '/ ':if(c== '( ')return ' < ';
else return '> ';
case '( ':if(c== ') ')return '= ';
else return ' < ';
case ') ':return '> ';
case '= ':if(c== '= ')return '= ';
else return ' < ';
default :break;
}
}
int Pop(SqStack2 &S,double &e)
{
if(S.top==S.base)return 0;
e=*--S.top;
return 1;
}
int Pop(SqStack1 &S,char &e)
{
if(S.top==S.base)return 0;
e=*--S.top;
return 1;
}
double Operate(double a,char theta,double b)
{
if(theta== '+ ')return a+b;
else if(theta== '* ')return a*b;
else if(theta== '/ ') return a/b;
else return a-b;
}
double EvaluateExpression(char ab[],double v[],int cd[])//ab是存放的符号，v是存放操作数，而cd存放的是哪个是符号，哪个是数字，
{
int i=0,j=0, k=0;
char theta;double a,b;char e;double d;
InitStack(OPTR);Push(OPTR, '= ');
InitStack(OPND);
while(ab[i]!= '= '||GetTop(OPTR,e)!= '= ')
{
if(cd[k++]==1)
Push(OPND,v[j++]);
else switch(Precede(GetTop(OPTR,e),ab[i]))
{
case ' < ':
Push(OPTR,ab[i++]);
break;
case '= ':
Pop(OPTR,*(OPTR.top-1));i++;
break;
case '> ':
Pop(OPTR,theta);
Pop(OPND,b);
Pop(OPND,a);
Push(OPND,Operate(a,theta,b));
k--;
break;
}
}
return GetTop(OPND,d);
}
void main()
{
double a;int i;int cd[30];int kg=0;
char b[200];
double v[50]={0.0};char c[50];int j=0,k=0,p=0;char f[20]={0};
double value;int q=0;
int flag=0;int ky=0;int ay;int w=0;
for( i=0;i <200&&b[i-1]!= '= ';i++)
{
b[i]=getchar();
}b[i]= '\0 ';
for(i=0;i <strlen(b);i++)
{
if(b[i]== '* '||b[i]== '+ '||b[i]== '/ '||b[i]== '- '||b[i]== '( '||b[i]== ') '||b[i]== '= ')
{
c[k++]=b[i];cd[kg++]=0;//k记录的是符号的个数
}
else
{
f[p++]=b[i];
if(b[i+1]== '* '||b[i+1]== '+ '||b[i+1]== '/ '||b[i+1]== '- '||b[i+1]== '( '||b[i+1]== ') '||b[i+1]== '= ')
{
for(q=0;q <p;q++)
{
if(f[q]== '. ')
{
flag=1;
break;
}
}
if(flag==1)
{
for(ay=0;ay <p;ay++)
{
if(f[ay]== '. ');
else
{
value=double(f[ay]- '0 ');
if(ay <q)
{
for(ky=ay+1;ky <q;ky++)
{
value=value*10;
}
v[w]=v[w]+value;
}
else
{
for(ky=q;ky <ay;ky++)
value=value*0.1;
v[w]=v[w]+value;
}
}
}
w++;p=0;cd[kg++]=1;f[0]= '\0 ';
}
else
{
for(ay=0;ay <p;ay++)
{
value=double(f[ay]- '0 ');
for(ky=1;ky <p-ay;ky++)
value=value*10;
v[w]=v[w]+value;//W记录的是勇于计算的个数。
}
w++;p=0;cd[kg++]=1;
flag=0;
}
}
}
}
a=EvaluateExpression(c,v,cd);
printf( "%f\n ",a);
}
[解决办法]
用TC2.0或者WinTC编译 ， 输入格式 22+1*(2+1*(2+1*(22+44)))=
int strlen(char s[])
{
int i=0;
while(s[i]!= '\0 ') i++;
return i;
}
int getResult (int a, int b, char op)
{
switch(op)
{
case '+ ': return a+b;
case '- ': return a-b;
case '* ': return a*b;
case '/ ': return a/b;
}/*switch*/
}/*getResult*/
int getPrior(char op)
{
switch(op)
{
case '+ ':
case '- ': return 1;
case '* ':
case '/ ': return 2;
case '( ': return 4;
case ') ': return 8;
case '= ': return 16;
default: return 0;
}/*switch*/
}/*getPrior*/
int getToken(char *exp, int b, int e)
{/*将exp[b..e]子字符串转换为int型并返回*/
int sum = 0;
int i;
for (i = b; i <= e; i++)
sum = 10*sum + exp[i]- '0 ';
return sum;
}/*getToken*/
int Compute(char * expression, int end)
{
int p=0; /*扫描表达式*/
int *numstack; char *opstack; /*操作数栈和运算符栈*/
int np=0, op=0; /*操作数栈和运算符栈顶指针*/
int new=0; /*是否出现一个新的操作数*/
int begin=0; /*新操作数的起始位 */
int prior, n1, n2;
int temp;
char operat;
numstack = (int *) malloc(sizeof(int)*(end+1));
opstack = (char *) malloc(sizeof(char)*(end+1)); /*预留足够栈空间*/
while( expression[p]!= '= ')
{
prior = getPrior(expression[p]);
switch(prior)
{
case 0: /*出现数字*/
if(!new) /*第一次出现*/
{ begin=p; /*记录起始位*/
new =1 ;
}/*if*/
if(getPrior(expression[p+1])) { /*检查下一个位置，非数字则转换压栈*/
new=0;
n1 = getToken(expression,begin,p);
numstack[np++] = n1; /*操作数压栈numstack*/
}/*if*/
break;
case 1:
if(getPrior(opstack[op-1]) <=2&&op> 0) /*运算符栈顶为 '+ ', '- ', '* ', '/ '*/
{
n1 = numstack[--np];
n2 = numstack[--np];
operat = opstack[--op];
n1 = getResult(n1,n2,operat);
numstack[np++]=n1; /*计算结果压入numstack*/
opstack[op++] = expression[p]; /*当前 '+ ', '- '压入opstack*/
}/*if*/
else if(getPrior(opstack[op-1])==4||op==0) /*运算符栈顶为 '( ' 或者是第一个操作符*/
{
/*直接简单压栈*/
opstack[op++] = expression[p];
}/*else if*/
break;
case 2:
if(expression[p+1]== '( ') /*若 '* ' '/ ' 紧接着 “（”*/
opstack[op++] = expression[p]; /*直接简单压栈*/
else /*取下一个数字*/
{
operat = expression[p];
temp=p+1;
while(!getPrior(expression[p+1]))
p++;
n2=getToken(expression,temp,p);
n1 = numstack[--np];
n1 = getResult(n1,n2,operat);
numstack[np++]=n1; /*计算结果压入numstack*/
}
break;
case 4:
opstack[op++] = expression[p]; /*直接简单压栈*/
break; /*当前扫描到 ') '*/
case 8:
if(opstack[op-1]!= '( ')
{
n1 = numstack[--np];
n2 = numstack[--np];
operat = opstack[--op];
n1 = getResult(n1,n2,operat);
numstack[np++]=n1; /*计算结果压入numstack*/
/*当前 '+ ', '- '压入opstack*/
}
--op; /*检查此时的栈顶运算符*/
if (op> =1&& np> =1) /*计算外层（）*/
{
n1 = numstack[--np];
n2 = numstack[--np];
operat = opstack[--op];
n1 = getResult(n1,n2,operat);
numstack[np++]=n1; /*计算结果压入numstack*/
/*当前 '+ ', '- '压入opstack*/
}
break;
}/*switch*/
p++;
}/*while*/
if(np> 1)
{ n2= numstack[--np];
n1= numstack[--np];
return getResult(n1,n2,opstack[--op]);
}
else return numstack[0];
}/*Compute*/
main()
{
char *s;
int p,len;
scanf( "%s ",s);
/* if(checkformat(s)) */
len= strlen(s);
p = Compute(s,len);
printf( " %d\n ",p);
getch();
}/*main*/
[解决办法]
不好意思 上面的程序有些Bug...我经过测试已经修正了 并且增加了checkformat（）这个函数,下面是完整的实现 用TC2.0编译通过：
int strlen(char s[])
{
int i=0;
while(s[i]!= '\0 ') i++;
return i;
}
int getResult (int a, int b, char op)
{
switch(op)
{
case '+ ': return a+b;
case '- ': return a-b;
case '* ': return a*b;
case '/ ': return a/b;
}/*switch*/
}/*getResult*/
int getPrior(char op)
{
switch(op)
{
case '+ ':
case '- ': return 1;
case '* ':
case '/ ': return 2;
case '( ': return 4;
case ') ': return 8;
case '= ': return -1;
default: return 0;
}/*switch*/
}/*getPrior*/
int getToken(char *exp, int b, int e)
{/*将exp[b..e]子字符串转换为int型并返回*/
int sum = 0;
int i;
for (i = b; i <= e; i++)
sum = 10*sum + exp[i]- '0 ';
return sum;
}/*getToken*/
int Compute(char * expression, int end)
{
int p=0; /*扫描表达式*/
int *numstack; char *opstack; /*操作数栈和运算符栈*/
int np=0, op=0; /*操作数栈和运算符栈顶指针*/
int new=0; /*是否出现一个新的操作数*/
int begin=0; /*新操作数的起始位 */
int prior, n1, n2;
int temp;
char operat;
numstack = (int *) malloc(sizeof(int)*(end+1));
opstack = (char *) malloc(sizeof(char)*(end+1)); /*预留足够栈空间*/
while( expression[p]!= '= ')
{
prior = getPrior(expression[p]);
switch(prior)
{
case 0: /*出现数字*/
if(!new) /*第一次出现*/
{ begin=p; /*记录起始位*/
new =1 ;
}/*if*/
if(getPrior(expression[p+1])) { /*检查下一个位置，非数字则转换压栈*/
new=0;
n1 = getToken(expression,begin,p);
numstack[np++] = n1; /*操作数压栈numstack*/
}/*if*/
break;
case 1:
if(getPrior(opstack[op-1]) <=2&&op> 0) /*运算符栈顶为 '+ ', '- ', '* ', '/ '*/
{
n1 = numstack[--np];
n2 = numstack[--np];
operat = opstack[--op];
n1 = getResult(n2,n1,operat);
numstack[np++]=n1; /*计算结果压入numstack*/
opstack[op++] = expression[p]; /*当前 '+ ', '- '压入opstack*/
}/*if*/
else if(getPrior(opstack[op-1])==4||op==0) /*运算符栈顶为 '( ' 或者是第一个操作符*/
{
/*直接简单压栈*/
opstack[op++] = expression[p];
}/*else if*/
break;
case 2:
if(expression[p+1]== '( ') /*若 '* ' '/ ' 紧接着 “（”*/
opstack[op++] = expression[p]; /*直接简单压栈*/
else /*取下一个数字*/
{
operat = expression[p];
temp=p+1;
while(!getPrior(expression[p+1]))
p++;
n2=getToken(expression,temp,p);
n1 = numstack[--np];
n1 = getResult(n1,n2,operat);
numstack[np++]=n1; /*计算结果压入numstack*/
}
break;
case 4:
opstack[op++] = expression[p]; /*直接简单压栈*/
break; /*当前扫描到 ') '*/
case 8:
if(opstack[op-1]!= '( ')
{
n1 = numstack[--np];
n2 = numstack[--np];
operat = opstack[--op];
n1 = getResult(n2,n1,operat);
numstack[np++]=n1; /*计算结果压入numstack*/
/*当前 '+ ', '- '压入opstack*/
}
--op; /*检查此时的栈顶运算符*/
if (op> =1&& np> =1 && getPrior(opstack[op-1])> =getPrior(expression[p+1])) /*计算外层（）*/
{
n1 = numstack[--np];
n2 = numstack[--np];
operat = opstack[--op];
n1 = getResult(n2,n1,operat);
numstack[np++]=n1; /*计算结果压入numstack*/
/*当前 '+ ', '- '压入opstack*/
}
break;
}/*switch*/
p++;
}/*while*/
if(np> 1)
{ n2= numstack[--np];
n1= numstack[--np];
return getResult(n1,n2,opstack[--op]);
}
else return numstack[0];
}/*Compute*/
int checkformat(char *exp)
{ int left=0; /* '( '出现的次数*/
int p=0; /*扫描表达式*/
int len=strlen(exp); /*表达式长度*/
while(p <len)
{
if(
(p==0&&exp[p] <= '9 '&&exp[p]> = '0 ')||
((p> 0&&exp[p] <= '9 '&&exp[p]> = '0 ')&&((exp[p-1]== '( ')||(getPrior(exp[p-1])> 0&&getPrior(exp[p-1]) <=2)))) /*出现一个数字*/
{
while(getPrior(exp[p+1])==0&&exp[p+1] <= '9 '&&exp[p+1]> = '0 ')
p++;
}/*if*/
else if(getPrior(exp[p])==0) /*出现其他非法字符,或者上一个字符为 ') '*/
{
return 0;
}/*else if*/
else if (exp[p]== '( ')
{
if((p> 0&&exp[p-1]== '( ')||p==0||(getPrior(exp[p-1])> 0&&getPrior(exp[p-1]) <=2))
left++;
else
return 0;
}/*else if*/
else if (exp[p]== ') ')
{
if((p> 0&&left> 0)&&(getPrior(exp[p-1])==0&&exp[p-1] <= '9 '&&exp[p-1]> = '0 ')||(exp[p-1]== ') '))
left--;
else
return 0;
}
else if ( getPrior(exp[p])> 0&&getPrior(exp[p]) <=2 )/*出现 '+ ', '- ', '* ', '/ '*/
{
if(p> 0&&((getPrior(exp[p-1])==0&&exp[p-1] <= '9 '&&exp[p-1]> = '0 ')||(exp[p-1]== ') '))) /*上一个是数字或者 ') '*/
{}
else
return 0;
}
else if ((left==0&&p> 0&&exp[p]== '= '&&p==len-1&&getPrior(exp[p-1])==0&&exp[p-1] <= '9 '&&exp[p-1]> = '0 ')
||(p> 0&&exp[p-1]== ') '&&left==0)) /*出现 "= "，长度为len并且上一个是数字*/
return 1;
else
return 0;
p++;
}/*while*/
}/*checkformat*/
main()
{
char *s;
int p,len;
scanf( "%s ",s);
if(checkformat(s))
{
len= strlen(s);
p = Compute(s,len);
printf( " %d\n ",p);
}
else
printf( "\nThis input is invalid! ");
}/*main*/
[解决办法]
还有一个bug ...这下就好了。。。
int strlen(char s[])
{
int i=0;
while(s[i]!= '\0 ') i++;
return i;
}
int getResult (int a, int b, char op)
{
switch(op)
{
case '+ ': return a+b;
case '- ': return a-b;
case '* ': return a*b;
case '/ ': return a/b;
}/*switch*/
}/*getResult*/
int getPrior(char op)
{
switch(op)
{
case '+ ':
case '- ': return 1;
case '* ':
case '/ ': return 2;
case '( ': return 4;
case ') ': return 8;
case '= ': return -1;
default: return 0;
}/*switch*/
}/*getPrior*/
int getToken(char *exp, int b, int e)
{/*将exp[b..e]子字符串转换为int型并返回*/
int sum = 0;
int i;
for (i = b; i <= e; i++)
sum = 10*sum + exp[i]- '0 ';
return sum;
}/*getToken*/
int Compute(char * expression, int end)
{
int p=0; /*扫描表达式*/
int *numstack; char *opstack; /*操作数栈和运算符栈*/
int np=0, op=0; /*操作数栈和运算符栈顶指针*/
int new=0; /*是否出现一个新的操作数*/
int begin=0; /*新操作数的起始位 */
int prior, n1, n2;
int temp;
char operat;
numstack = (int *) malloc(sizeof(int)*(end+1));
opstack = (char *) malloc(sizeof(char)*(end+1)); /*预留足够栈空间*/
while( expression[p]!= '= ')
{
prior = getPrior(expression[p]);
switch(prior)
{
case 0: /*出现数字*/
if(!new) /*第一次出现*/
{ begin=p; /*记录起始位*/
new =1 ;
}/*if*/
if(getPrior(expression[p+1])) { /*检查下一个位置，非数字则转换压栈*/
new=0;
n1 = getToken(expression,begin,p);
numstack[np++] = n1; /*操作数压栈numstack*/
}/*if*/
break;
case 1:
if(getPrior(opstack[op-1]) <=2&&op> 0) /*运算符栈顶为 '+ ', '- ', '* ', '/ '*/
{
n1 = numstack[--np];
n2 = numstack[--np];
operat = opstack[--op];
n1 = getResult(n2,n1,operat);
numstack[np++]=n1; /*计算结果压入numstack*/
opstack[op++] = expression[p]; /*当前 '+ ', '- '压入opstack*/
}/*if*/
else if(getPrior(opstack[op-1])==4||op==0) /*运算符栈顶为 '( ' 或者是第一个操作符*/
{
/*直接简单压栈*/
opstack[op++] = expression[p];
}/*else if*/
break;
case 2:
if(expression[p+1]== '( ') /*若 '* ' '/ ' 紧接着 “（”*/
opstack[op++] = expression[p]; /*直接简单压栈*/
else /*取下一个数字*/
{
operat = expression[p];
temp=p+1;
while(!getPrior(expression[p+1]))
p++;
n2=getToken(expression,temp,p);
n1 = numstack[--np];
n1 = getResult(n1,n2,operat);
numstack[np++]=n1; /*计算结果压入numstack*/
}
break;
case 4:
opstack[op++] = expression[p]; /*直接简单压栈*/
break; /*当前扫描到 ') '*/
case 8:
if(opstack[op-1]!= '( ')
{
n1 = numstack[--np];
n2 = numstack[--np];
operat = opstack[--op];
n1 = getResult(n2,n1,operat);
numstack[np++]=n1; /*计算结果压入numstack*/
/*当前 '+ ', '- '压入opstack*/
}
--op; /*检查此时的栈顶运算符*/
if (op> =1&& np> =1 && opstack[op-1]!= '( '&& (expression[p+1]== ') '||getPrior(opstack[op-1])> =getPrior(expression[p+1]))) /*计算外层（）*/
{
n1 = numstack[--np];
n2 = numstack[--np];
operat = opstack[--op];
n1 = getResult(n2,n1,operat);
numstack[np++]=n1; /*计算结果压入numstack*/
/*当前 '+ ', '- '压入opstack*/
}
break;
}/*switch*/
p++;
}/*while*/
if(np> 1)
{ n2= numstack[--np];
n1= numstack[--np];
return getResult(n1,n2,opstack[--op]);
}
else return numstack[0];
}/*Compute*/
int checkformat(char *exp)
{ int left=0; /* '( '出现的次数*/
int p=0; /*扫描表达式*/
int len=strlen(exp); /*表达式长度*/
while(p <len)
{
if(
(p==0&&exp[p] <= '9 '&&exp[p]> = '0 ')||
((p> 0&&exp[p] <= '9 '&&exp[p]> = '0 ')&&((exp[p-1]== '( ')||(getPrior(exp[p-1])> 0&&getPrior(exp[p-1]) <=2)))) /*出现一个数字*/
{
while(getPrior(exp[p+1])==0&&exp[p+1] <= '9 '&&exp[p+1]> = '0 ')
p++;
}/*if*/
else if(getPrior(exp[p])==0) /*出现其他非法字符,或者上一个字符为 ') '*/
{
return 0;
}/*else if*/
else if (exp[p]== '( ')
{
if((p> 0&&exp[p-1]== '( ')||p==0||(getPrior(exp[p-1])> 0&&getPrior(exp[p-1]) <=2))
left++;
else
return 0;
}/*else if*/
else if (exp[p]== ') ')
{
if((p> 0&&left> 0)&&(getPrior(exp[p-1])==0&&exp[p-1] <= '9 '&&exp[p-1]> = '0 ')||(exp[p-1]== ') '))
left--;
else
return 0;
}
else if ( getPrior(exp[p])> 0&&getPrior(exp[p]) <=2 )/*出现 '+ ', '- ', '* ', '/ '*/
{
if(p> 0&&((getPrior(exp[p-1])==0&&exp[p-1] <= '9 '&&exp[p-1]> = '0 ')||(exp[p-1]== ') '))) /*上一个是数字或者 ') '*/
{}
else
return 0;
}
else if ((left==0&&p> 0&&exp[p]== '= '&&p==len-1&&getPrior(exp[p-1])==0&&exp[p-1] <= '9 '&&exp[p-1]> = '0 ')
||(p> 0&&exp[p-1]== ') '&&left==0)) /*出现 "= "，长度为len并且上一个是数字*/
return 1;
else
return 0;
p++;
}/*while*/
}/*checkformat*/
main()
{
char *s;
int p,len;
scanf( "%s ",s);
if(checkformat(s))
{
len= strlen(s);
p = Compute(s,len);
printf( " %d\n ",p);
}
else
printf( "\nThis input is invalid! ");
}/*main*/
[解决办法]
呵呵，我做过这个题目，用的是两个链表实现的，一个存放数据，另外的存放运算符，
