数据结构c语言版表达式求值标准程序

C语言编程（数据结构）:表达式求值~

/*在TC2 和 VC6下都可以顺利运行。
做了一个下午。一定要用我这个噢。
有简单的输入错误检测。有完整的说明和
注释*/

#include<stdio.h> /*库文件包含*/
#include<string.h> /*用于字符串操作*/
#include<stdlib.h> /*用于exit函数*/

/**************************************************************************
int check(char *c)
输入参数：
char *c: 输入的字符串
返回参数：
0：字符串中有不符合规定的字符
1: 字符串字符符合规定，没有不符合规定的字符.
功能：
检查字符串中有否除了 0-9, +,-,*,/,(,),之外的其他字符，
如果有，则返回0, 表示出现错误。
若没有，则返回1,表式字符串符合规定。
**************************************************************************/
int check(char *c)
{
int k=0;
while(*c!='\0')
{
if((*c>='0' && *c<='9') || *c=='+' ||
*c=='-' || *c=='*' || *c=='/' ||
*c=='.' || *c=='(' || *c==')' )
{

}
else
{
printf("input error, there have the char not the math expression char!
");
return 0;
}

if(*c=='(')
k++;
else if(*c==')')
k--;

c++;
}
if(k!=0)
{
printf("input error, there is not have correct bracket '()'!
");
return 0;
}
return 1;
}

/**************************************************************************
void move(char *f, double *s,int p)

输入参数：
char *f : 运算符数组
double *s: 数值数组
int p: 当前运算符数组位置。
返回参数:
无
功能：
将当前已经完成运算的运算符消去，同时将数值数组的位置调整以进行下一次运算。
传入值p若为3
则当前符号的数组位置为3.
f[3]=f[3+1].......f[len-2]=f[len-1] f[len-1]='\0';
s[i]=s[i+1].......s[len-1]=s[len] 因为数值比运算符多一个。
***************************************************************************/

void move(char *f, double *s,int p)
{
int i=0,len=strlen(f);
for(i=p; i<len; i++) /*将已经运算过的符号，空出来的位置用后面的符号来填充，*/
{ /*即把乘和除号的位置用后面的加和减号填充*/
f[i]=f[i+1];
s[i]=s[i+1];
}
s[i]=s[i+1];
f[len-1]='\0';
}
/**************************************************************************
double convnum(char *c)
输入参数：
char *c :由数字和小数点组成的字符，用以转换成double型的数值。
返回参数：
num:返回转换好的值。
功能：
将输入的字符串先将其小数点以前的部分复制到temp[]数组中，
若有小数点，则将小数点之后的数值，也就是小数部分先进行计算,值存入num中
计算完成后，再对整数部分进行计算，值加上小数部分的值，存入num中。
***************************************************************************/
double convnum(char *c)
{
double num=0.0;
double a=1.0;
int i=0,p=0,len=0;
char temp[100];
int tempi=0;
int start=0;
int f=1; /*正负符号指示器，若为1则为正数，为－1，此数为负数*/

len=strlen©;

if(c[0]=='-')
{
start=1;
f=-1;
}
for(i=start; i<len; i++)
{
if(c[i]=='.')
{
p=i;
break;
}
temp[tempi++]=c[i]; /*将整数部分复制到temp[]中*/
}
temp[tempi]='\0';

if(p!=0)
{
for(i=p+1;i<len;i++) /*将小数部分计算出来*/
{
if(c[i]=='.') /*如果有多余的小数点，则表示输入错误*/
{
printf("there is more that one dot '.' in number!error!
");
exit(0);
}
a=a*0.1;
num+=(a*(c[i]-48));
}
}

a=1.0;

len=strlen(temp); /*计算整数部分*/
for(i=len-1;i>=0; i--)
{
num=num+(a*(temp[i]-48));
a*=10;
}

num=num*f;
return num;
}

/**************************************************************************
double good(char *c)
输入参数：
char *c :即将进行运算的字符串型数学表达式。如3.5+(2*3/5)
返回参数：
s[0]:计算结果将放入s[0]中
功能：
将输入的字符串中的数字分别调用convnum(char *c)函数进行数值变换，再将其依
次存入doulbe s[i]中，将加减乘除运算符依次存入字符串符号数组 char f[i]中，
然后如果遇到括号，则将括号内的字符串存入另一字符数组中，然后用此
good(char *c) 递归函数进行递归运算。 然后根据先乘除，后加减的顺序对已
存入数组的数值根 据存入字符串符号数组的运算符进行运算。结果存入s[0]中。
返回最终结果。
***************************************************************************/
double good(char *c) /*可递归函数*/
{ /*取得数值字符串，并调用convnum转换成double*/
char g[100],number[30]; /*g,保存当前的表达式串,number保存一个数的所有字符*/
char f[80]; /*保存所有的符号的堆栈*/
int fi=0; /*保存符号的位置指针*/
double s[80]; /*保存当前所有的数的一个堆栈*/
int si=0; /*保存数字位置指针*/
int k=0; /* 若k=1则表示有一对括号*/
int num=0,i=0; /*num保存新括号内的字符数,i 保存number里的字符位置*/
int cc=0; /*乘除符号数量*/
int jj=0; /*加减符号数量*/

while(*c!='\0')/*当p==1 和k==0时，表示已经把括号里的内容全部复制到g[100]中了*/
{
k=0;
num=0;

switch(*c)
{
case '+': /*当前字符为+-乘除时则表示*/
case '-':
case '*':
case'/':
f[fi++]=*c;
if(*c=='*' || *c=='/')
cc++;
else
jj++;
if(*(c-1)!=')')
{
number[i]='\0';
i=0;/*完成一个数字的复制，其位置指针i=0*/

s[si++]=convnum(number);
}
break;
case'(': /*有括号，则将当前括号作用范围内的全部字符保存，作为*/
k++; /*一个新的字符表达式进行递归调用good函数计算。*/
while(k>0)
{
c++;
g[num]=*c;
num++;
if(*c==')')
{
k--;
}
else if(*c=='(')
{
k++;
}
}
g[num-1]='\0';
num=0;/*完成一个括号内容的复制，其位置指针num=0*/
s[si++]=good(g);
break;
default:
number[i++]=*c;

if(*(c+1)=='\0')
{ number[i]='\0';
s[si++]=convnum(number);
}
break;
}

c++;
}

f[fi]='\0';

i=0;
while(cc>0)
{
switch(f[i])
{
case '*': cc--;
s[i+1]=s[i]*s[i+1];
move(f,s,i);
break;
case '/': cc--;
s[i+1]=s[i]/(float)s[i+1];
move(f,s,i);
break;
default:
i++;
break;
}
}

i=0;
while(jj>0)
{
switch(f[i])
{
case '+': s[i+1]=s[i]+s[i+1];
jj--;
move(f,s,i);
break;
case '-': s[i+1]=s[i]-s[i+1];
jj--;
move(f,s,i);
break;
default:
printf("operator error!");
break;
}
}

return s[0];
}

void main()
{
char str[100];
double sum=0;
int p=1;

while(1)
{
printf("enter expression: enter 'exit' end of program
");
scanf("%s",str);
p=strcmp(str,"exit");
if(p==0)
break;
p=check(str);

if(p==0)
continue;
sum=good(str);
printf("%s=%f",str,sum);
printf("
");
}
printf("good bye!
");
}

例：
enter expression: enter 'exit' end of program
3.5+(12.3*15+8-(3/2+1))*2+(3.2*3-5)/6(输入)
3.5+(12.3*15+8-(3/2+1))*2+(3.2*3-5)/6=384.266667
enter expression: enter 'exit' end of program
china(输入)
input error, there have the char not the math expression char!
enter expression: enter 'exit' end of program
exit(输入)
good bye!

用栈把中缀表达式(输入的式子）按优先级转为后缀表达式（逆波兰式，即运算符在前，操作数在后），再利用栈变计算边保存结果用于下一步计算，最后算出式子的答案
以下代码输入一个式子（以
=
作为输入结束标志），输出结果，负数如-3用0-3表示，支持高位运算
#include

#include

#include

#include

#define
OK
1
#define
ERROR
-1
typedef
char
SElemType;
typedef
char
Status;
#define
STACK_INIT_SIZE
100000
#define
STACKINCREMENT
2
struct
SqStack
{
SElemType
*base;
SElemType
*top;
int
stacksize;
};
struct
SqStack1
{
int
*base;
int
*top;
int
stacksize;
};
SqStack
OPTR;
SqStack1
OPND;
char
Precede(char
c1,char
c2)
{
if(c1=='+'
||
c1=='-')
{
if(c2=='+'
||
c2=='-'
||
c2==')'
||
c2=='=')
return
'>';
else
return
'<';
}
else
if(c1=='*'
||
c1=='/')
{
if(c2=='(')
return
'<';
else
return
'>';
}
else
if(c1=='(')
{
if(c2==')')
return
'=';
else
return
'<';
}
else
if(c1==')')
return
'>';
else
if(c1=='=')
{
if(c2=='=')
return
'=';
else
return
'<';
}
else
return
'\0';
}
int
In(char
c)
{
if(c=='+'
||
c=='-'
||
c=='*'
||
c=='/'
||
c=='('
||
c==')'
||
c=='=')
return
1;
else
return
0;
}
int
Operrate(int
m,char
b,int
n)
{
switch(b)
{
case
'+':return
m+n;
case
'-':return
m-n;
case
'*':return
m*n;
case
'/':return
m/n;
}
return
0;
}
//操作数
int
InitStack1(SqStack1
&S)
{
S.base=(int
*)malloc(STACK_INIT_SIZE*sizeof(int));
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return
OK;
}
int
Push1(SqStack1
&S,int
e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(int
*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
S.top=S.base+S.stacksize;
S.stacksize=S.stacksize+STACKINCREMENT;
}
*S.top++=e;
return
OK;
}
int
Pop1(SqStack1
&S,int
&e)
{
if(S.top==S.base)
return
ERROR;
e=*
--S.top;
return
OK;
}
int
GetTop1(SqStack1
S)
{
if(S.top==S.base)
return
ERROR;
return
*(S.top-1);
}
//算符
int
InitStack(SqStack
&S)
{
S.base=(SElemType
*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return
OK;
}
int
Push(SqStack
&S,SElemType
e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType
*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
S.top=S.base+S.stacksize;
S.stacksize=S.stacksize+STACKINCREMENT;
}
*S.top++=e;
return
OK;
}
int
Pop(SqStack
&S,SElemType
&e)
{
if(S.top==S.base)
return
ERROR;
e=*
--S.top;
return
OK;
}
Status
GetTop(SqStack
S)
{
if(S.top==S.base)
return
ERROR;
return
*(S.top-1);
}
int
Calculate()
{
char
c,theta,p;
int
a,b,i=0,ans,x;
InitStack(OPTR);
Push(OPTR,'=');
InitStack1(OPND);
c=getchar();
while(c!='='
||
GetTop(OPTR)!='=')
{
if(!In(c)
&&
c>='0'
&&
c<='9')
{
Push1(OPND,c-'0');
c=getchar();
while(c>='0'
&&
c<='9')
{
Pop1(OPND,x);
Push1(OPND,x*10+c-'0');
c=getchar();
}
}
else
if(In(c))
{
switch(Precede(GetTop(OPTR),c))
{
case
'<':
Push(OPTR,c);
c=getchar();
break;
case
'=':
Pop(OPTR,p);
c=getchar();
break;
case
'>':
Pop(OPTR,theta);
Pop1(OPND,b);
Pop1(OPND,a);
ans=Operrate(a,theta,b);
Push1(OPND,ans);
break;
}
}
else
{
c=getchar();
}
}
return
GetTop1(OPND);
}
int
main()
{
int
ans;
ans=Calculate();
printf("%d
",ans);
return
0;
}

思路：中缀表达式－后缀表达式－求值

参考代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iterator>
#include <algorithm>

// 堆栈的数组实现，数组的大小固定。
template<class T>
class stack
{
private:
T *s; // 数组的首地址（栈底）
size_t N; // 指向栈顶第一个空闲块
const size_t size; // 堆栈的大小，固定不变

public:
stack(size_t n) : size(n)
{
s = new T[n]; // 可能抛出异常
N = 0; // 设置栈顶指针
}

~stack()
{
delete [] s;
}

bool empty() const
{
return N == 0;
}

bool full() const
{
return N == size;
}

void push(const T &object)
{
if (full())
{
throw "error: stack is full !";
}

s[N++] = object;
}

T pop()
{
if (empty())
{
throw "error: stack is empty !";
}

return s[--N];
}

T peek() const
{
if (empty())
{
throw "error: stack is empty !";
}

return s[N-1];
}

friend std::ostream& operator<<(std::ostream& os, const stack<T> &stk)
{
for (size_t i = 0; i < stk.N; i++)
{
std::cout << stk.s[i] << " ";
}

return os;
}
};

// 堆栈的链表实现
template<class T>
class STACK
{
private:
typedef struct node
{
T item;
node *next;
node(T x, node *t = NULL) : item(x), next(t) {}
}*link;

link head; // 指向栈顶第一个有效对象

public:
STACK(size_t n)
{
head = NULL;
}

~STACK() // 也可以用pop的方法删除，但效率低
{
link t = head;

while (t != NULL)
{
link d = t;
t = t->next;
delete d;
}
}

bool empty() const
{
return head == NULL;
}

bool full() const
{
return false;
}

void push(const T &object)
{
head = new node(object, head);
}

T pop()
{
if (empty())
{
throw "error: stack is empty !";
}

T v = head->item;
link t = head->next;
delete head;
head = t;
return v;
}

T peek() const
{
if (empty())
{
throw "error: stack is empty !";
}

return head->item;
}

friend std::ostream& operator<<(std::ostream& os, const STACK<T> &stk)
{
for (link t = stk.head; t != NULL; t = t->next)
{
std::cout << t->item << " ";
}

return os;
}
};

// 中缀表达式转化为后缀表达式，仅支持加减乘除运算、操作数为1位十进制非负整数的表达式。
char* infix2postfix(const char *infix, char *postfix)
{
const size_t N = strlen(infix);

if (N == 0 || postfix == NULL)
{
return postfix;
}

stack<char> opcode(N); // 堆栈存放的是操作符

for (size_t i = 0; i < N; i++)
{
switch (infix[i])
{
case '(': // 直接忽略左括号
break;

case ')': // 弹出操作符
*postfix++ = opcode.pop();
*postfix++ = ' ';
break;

case '+':
case '-':
case '*':
case '/':
opcode.push(infix[i]); // 压入操作符
break;

default:
if (isdigit(infix[i])) // 如果是数字，直接输出
{
*postfix++ = infix[i];
*postfix++ = ' ';
}
}
}

return postfix;
}

// 后缀表达式转化为中缀表达式，仅支持加减乘除运算、操作数为1位十进制非负整数的表达式。
char* postfix2infix(const char *postfix, char *infix)
{
const size_t N = strlen(postfix);

if (N == 0 || infix == NULL)
{
return infix;
}

*infix = '\0'; // 初始化输出字符串为空串
std::vector<std::string> v;

// 初始化，将所有有效字符放入容器
for (size_t i = 0; i < N; i++)
{
if (isdigit(postfix[i]) || postfix[i] == '+'
|| postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/')
{
v.push_back(std::string(1, postfix[i]));
}
}

// 处理每一个操作符
for (std::vector<std::string>::iterator b = v.begin(); b < v.end(); b++)
{
if (*b == "+" || *b == "-" || *b == "*" || *b == "/")
{
copy(v.begin(), v.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
std::cout << "------------------------------------------------" << std::endl;

std::string opcode = *(b);
std::string oprand1 = *(b - 2);
std::string oprand2 = *(b - 1);
b = v.erase(b - 2, b + 1); // 删除原来的三个表达式，用一个新的表达式替换
b = v.insert(b, std::string("(") + oprand1 + opcode + oprand2 + std::string(")"));
}
}

for (std::vector<std::string>::iterator b = v.begin(); b < v.end(); b++)
{
strcat(infix, (*b).c_str());
}

return infix;
}

// 计算后缀表达式的值，仅支持加减乘除运算、操作数为非负整数的表达式。
int postfix_eval(const char * postfix)
{
const size_t N = strlen(postfix);

if (N == 0)
{
return 0;
}

STACK<int> operand(N); // 堆栈存放的是操作数

for (size_t i = 0 ; i < N; i++)
{
switch (postfix[i])
{
int op1, op2;

case '+':
op1 = operand.pop();
op2 = operand.pop();
operand.push(op1 + op2);
break;

case '-':
op1 = operand.pop();
op2 = operand.pop();
operand.push(op1 - op2);
break;

case '*':
op1 = operand.pop();
op2 = operand.pop();
operand.push(op1 * op2);
break;

case '/':
op1 = operand.pop();
op2 = operand.pop();
operand.push(op1 / op2);
break;

default:

if (isdigit(postfix[i])) // 执行类似atoi()的功能
{
operand.push(0);

while (isdigit(postfix[i]))
{
operand.push(10 * operand.pop() + postfix[i++] - '0');
}

i--;
}
}

std::cout << operand << std::endl; // 输出堆栈的内容
}

return operand.pop();
}

// 本程序演示了如何后缀表达式和中缀表达式的相互转换，并利用堆栈计算后缀表达式。
// 转换方向：org_infix --> postfix --> infix
int main(int argc, const char *argv[])
{
// const char *org_infix = "(5*(((9+8)*(4*6))+7))"; // section 4.3
const char *org_infix = "(5*((9*8)+(7*(4+6))))"; // exercise 4.12
std::cout << "原始中缀表达式：" << org_infix << std::endl;

char *const postfix = new char[strlen(org_infix) + 1];
infix2postfix(org_infix, postfix);
std::cout << "后缀表达式：" << postfix << std::endl;

char *const infix = new char[strlen(postfix) + 1];
postfix2infix(postfix, infix);
std::cout << "中缀表达式：" << infix << std::endl;

std::cout << "计算结果是：" << postfix_eval(postfix) << std::endl;
std::cout << "计算结果是：" << postfix_eval("5 9*8 7 4 6+*2 1 3 * + * + *") << std::endl; // exercise 4.13

delete []infix;
delete []postfix;
return 0;
}

我的思路也是先求中缀表达式,之后再求解.
而且能计算多位数 ,小数...

有1个.h文件里面的内容是
//------------------------------------------------------------------
#ifndef STACK //避免重复包含
#define STACK

#define Stack_init_size 100
#define StackIncreament 10
//定义一个栈类型
typedef struct
{
float *base;
float *top;
int stacksize;
}Sqstack;
//定义栈的基本操作
int InitStack(Sqstack &s);
int DestroyStack(Sqstack &s);
int StackEmpty(Sqstack s);
int GetTop(Sqstack s,float &e);
int Push(Sqstack &s,float e);
int Pop(Sqstack &s,float &e);

#endif
//-----------------------------------------------------------------

一个.cpp文件
实现.h文件里面函数的基本操作
//-----------------------------------------------------------------
#include"Stack.h"
#include<stdlib.h>
int InitStack(Sqstack &s)
{
s.base=(float *)malloc(Stack_init_size*sizeof(float));
if(!s.base) exit(1);
s.top=s.base;
s.stacksize=Stack_init_size;
return 1;
}
int DestroyStack(Sqstack &s)
{
if(!s.base) return 0;
free(s.base);
s.base=s.top=0;
s.stacksize=0;
return 1;
}
int StackEmpty(Sqstack s)
{
if(s.base&&s.top==s.base) return 1;
else return 0;
}
int GetTop(Sqstack s,float &e)
{
if(StackEmpty(s)) return 0;
e=*(s.top-1);
return 1;
}
int Push(Sqstack &s,float e)
{
if(s.top-s.base>=s.stacksize)
{
s.base=(float *)realloc(s.base,(s.stacksize+StackIncreament)*sizeof(float));
if(!s.base) exit(1);
s.top=s.base+s.stacksize;
s.stacksize+=StackIncreament;
}
*s.top++=e;
return 1;
}
int Pop(Sqstack &s,float &e)
{
if(s.top==s.base) return 0;
e=*--s.top;
return 1;
}
//----------------------------------------------------------------
最后一个.cpp文件实现转化成后缀表达式,再求解
//----------------------------------------------------------------
#include"Stack.h"
#include<iostream>
#include<stdlib.h>
using namespace std;
////////定义函数实现对两操作符优先级的比较//////////
char precede(char c1,char c2)
{
if((c1=='+'||c1=='-')&&(c2=='+'||c2=='-'||c2==')'||c2=='#'))
return '>';
if((c1=='*'||c1=='/'||c1==')')&&(c2=='+'||c2=='-'||c2=='*'||c2=='/'||c2==')'||c2=='#'))
return '>';
if((c1=='('&&c2==')')||(c1=='#'&&c2=='#'))
return '=';
return '<';
}
//----定义转换函数(由原表达式得到逆波兰式)--------------
//---exp传入原表达式存放位置，suffix为转换后存放的地址-------
void transform(char *suffix, char *exp)
{
Sqstack S;
InitStack(S);Push(S,'#');
char *p=exp; char ch=*p;
int i=0;float c;
while(!StackEmpty(S))
{
if(!(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#'))
suffix[i++]=ch;
else
{
GetTop(S,c);
switch(ch)
{
case '(':
Push(S,ch);break;
case ')':
Pop(S,c);
while(c!='(')
{
suffix[i++]=c;Pop(S,c);
}
break;
default:
while(GetTop(S,c)&&(precede(c,ch)=='>'))
{
suffix[i++]=c;Pop(S,c);
}
if(ch!='#')
{
Push(S,ch);
suffix[i++]=' ';
}
break;
}
}
if(ch=='#')
{
Pop(S,c);
suffix[i++]=ch;
}
else
{
p++;
ch=*p;
}
}
suffix[i]='\0';
DestroyStack(S);
}

float Evaluate(char *exp)
{
Sqstack S;
InitStack(S);
char *p=exp, ch=*p;
float a,b;
char x[10];
int i=0,flag=0;
while(ch!='#')
{
while(!(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#'||ch==' '))
{
x[i++]=ch;
p++;ch=*p;
flag=1;
}
x[i]='\0';
i=0;
// cout<<x<<' ';
if(flag)
Push(S,atof(x));
if((ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#'))
{
Pop(S,b);Pop(S,a);
switch(ch)
{
case '+':Push(S,a+b);break;
case '-':Push(S,a-b);break;
case '*':Push(S,a*b);break;
case '/':Push(S,a/b);break;
}
}
p++;ch=*p;flag=0;
}
Pop(S,a);
DestroyStack(S);
return a;
}
//==========main的定义===========
void main()
{
char expression[80],result[80];
cout<<"input the expression:";
cin>>expression;
transform(result,expression);
cout<<result<<endl;
cout<<Evaluate(result);
}

//----------------------------------------------------------------

百分之百能运行成功...

---

数据结构c语言版表达式求值标准程序视频