c語言棧的表達式求值
A. C語言關於表達式求值
這是我以前做的一個表達式求值的程序,要求和實現的功能是一樣的:
#include<stdio.h>
#include <string.h>
#include <conio.h>
#define PLUS 0
#define MINUS 1
#define POWER 2
#define DIVIDE 3
#define LEFTP 4
#define RIGHP 5
#define STARTEND 6
#define DIGIT 7
#define POINT 8
#define NUM 7
#define NO 32767
#define STACKSIZE 20
char a[]={'+','-','*','/','(',')','#'};
int PriorityTable[7][7]={{ 1, 1,-1,-1,-1, 1, 1},
{ 1, 1,-1,-1,-1, 1, 1},
{ 1, 1, 1, 1,-1, 1, 1},
{ 1, 1, 1, 1,-1, 1, 1},
{-1,-1,-1,-1,-1, 0, NO},
{ 1, 1, 1, 1,NO, 1, 1},
{-1,-1,-1,-1,-1,NO, 0}};
int menu(void);
void InputExpression(char str[])
{
int len;
printf("Input expression string:\n");
scanf("%s",str);
len=strlen(str);
str[len]='#';
str[len+1]='\0';
}
int GetCharType(char ch)
{
int i;
for(i=0;i<NUM;i++) if(ch==a[i]) return(i);
if(ch>='0' && ch<='9') return(DIGIT);
if(ch=='.') return(POINT);
return(-1);
}
double Operate(double a,int theta,double b)
{
double x;
switch(theta)
{
case 0:x=a+b;break;
case 1:x=a-b;break;
case 2:x=a*b;break;
case 3:x=a/b;break;
}
return (x);
}
int EXCUTE(char *str,double *Result)
{
int pp,strlength,topTr,topNd,CharType,OPTR[STACKSIZE];
double number,temp,OPND[STACKSIZE];
OPTR[0]=STARTEND;
topTr=1;
topNd=0;
pp=0;
while((str[pp]))
{
CharType=GetCharType(str[pp]);
switch(CharType)
{
case -1:
return(0);
case DIGIT:
number=0;
while(str[pp]>='0' && str[pp]<='9')
{
number=number*10+(str[pp]-48);
pp++;
}
if(str[pp]=='.')
{
temp=10.0;
pp++;
while(str[pp]>='0' && str[pp]<='9')
{
number=number+(str[pp]-48)/temp;
temp=temp*10;
pp++;
}
}
OPND[topNd]=number;
topNd++;
break;
case POINT:
number=0;
temp=10.0;
pp++;
while(str[pp]>='0' && str[pp]<='9')
{
number=number+(str[pp]-48)/temp;
temp=temp*10;
pp++;
}
OPND[topNd]=number;
topNd++;
break;
case PLUS:
case MINUS:
case POWER:
case DIVIDE:
if(PriorityTable[OPTR[topTr-1]][CharType]==-1)
{
OPTR[topTr]=CharType;
topTr++;
pp++;
}
else
{
OPND[topNd-2]=Operate(OPND[topNd-2],OPTR[topTr-1],OPND[topNd-1]);
topNd--;
topTr--;
}
break;
case LEFTP:
OPTR[topTr]=CharType;
topTr++;
pp++;
break;
case RIGHP:
while(OPTR[topTr-1]!=LEFTP)
{
if(OPTR[topTr-1]==STARTEND)return(0);
if(PriorityTable[OPTR[topTr-1]][CharType]==1)
{
OPND[topNd-2]=Operate(OPND[topNd-2],OPTR[topTr-1],OPND[topNd-1]);
topNd--;
topTr--;
}
else
break;
}
topTr--;
pp++;
break;
case STARTEND:
while(OPTR[topTr-1]!=STARTEND)
{
OPND[topNd-2]=Operate(OPND[topNd-2],OPTR[topTr-1],OPND[topNd-1]);
topNd--;
topTr--;
}
if(topNd==1)
{
*Result=OPND[0];
return(1);
}
else
return(0);
}
}
return(1);
}
void main()
{ int num,flag;
double result;
char str[256];
str[0]='0';
while(1)
{ num=menu();
switch(num)
{
case 1:
InputExpression(str);
flag=0;
printf("%s\n",str);
getchar();
break;
case 2:
if(str[0]=='0')
{ printf("Expression is Empty!");
getchar();
break;
}
if(!EXCUTE(str,&result))
{ printf("The expression has error!\n");
getchar();
}
else
{ printf("calulation has finished!\n");
getchar();
flag=1;
}
break;
case 3:
if(flag)
{ printf("#%s=%lf\n",str,result);
getchar();
}
break;
case 4:
break;
}
if(num==4) break;
}
}
int menu(void)
{
int num;
printf("%20c1--input expression\n",' ');
printf("%20c2--calculation expression\n",' ');
printf("%20c3--print result\n",' ');
printf("%20c4--Quit\n",' ');
printf(" please select 1,2,3,4:");
do
{
scanf("%d",&num);
}while(num<1 || num>4);
return(num);
}
B. C語言 任意表達式求值。(棧的應用
/*** 只適合整數的表達式求值 ***/
/***其中部分可作修改,表達式也可是輸入的***/
#include "iostream.h"
const int n0=30;
int s1[n0+1]; //操作數棧
char s2[n0+1]; //運算符棧
int t1,t2;
int num[4]; //提取表達式中的整數
void calcu() //一次計算
{
int x1,x2,x;
char p;
//彈出一個運算符
p=s2[t2--];
//彈出兩個操作數
x2=s1[t1--];
x1=s1[t1--];
//進行一次運算
switch(p) {
case '+':x=x1+x2;break;
case '-':x=x1-x2;break;
case '*':x=x1*x2;break;
case '/':x=x1/x2;
}
//結果壓入操作數棧
s1[++t1]=x;
}
int calculator(char *f)
{
int v,i=0;
char *p=f;
t1=t2=0; //設置空棧
while (*p!='\0')
switch(*p) {
case '+': case '-':
while (t2&&(s2[t2]!='('))
//執行先遇到的加、減、乘、除運算
calcu();
//當前運算符進棧
s2[++t2]=*p;
//讀下一個字元
p++;
break;
case '*': case '/':
if (t2&&(s2[t2]=='*')||(s2[t2]=='/'))
//執行先遇到的乘、除運算
calcu();
//當前運算符進棧
s2[++t2]=*p;
//讀下一個字元
p++;
break;
case '(':
//左括弧進棧
s2[++t2]=*p;
//讀下一個字元
p++;
break;
case ')':
while (s2[t2]!='(')
//執行括弧內的加、減、乘、除運算
calcu();
//彈出左括弧
t2--;
//讀下一個字元
p++;
break;
default:
//把字元串轉換成整數值
v=0;
do {
v=10*v+*p-'0';
p++;
} while((*p>='0')&&(*p<='9'));
//操作數進棧
s1[++t1]=v;
num[i++]=v;
};
//執行先遇到的加、減、乘、除運算
while (t2) calcu();
//返回結果
return s1[t1];
}
void main()
{
char a[]="5*(40+6)-39";
cout<<calculator(a)<<endl;
cout<<"其中的數字為:\n";
for (int i=0;i<4;i++)
{
cout<<num[i]<<' ';
}
cout<<endl;
}
原來做過的東西,是C++的,VC++6.0環境下調試運行成功。