表达式求值算法
1. 栈的应用 表达式求值
您好，// 判断c是否为运算符
int In(SElemType c)
{
switch(c)
{
case'+':
case'-':
case'*':
case'/':
case'(':
case')':
case'#':return 1;
default:return 0;
}
}
SElemType Operate(SElemType a,SElemType theta,SElemType b)
{
SElemType c;
a=a-48; //ASCII值转化为对应的十进制值
b=b-48; //ASCII值转化为对应的十进制值
switch(theta)
{
case'+':
c=a+b+48;
break;
case'-':
c=a-b+48;
break;
case'*':
c=a*b+48;
break;
case'/':c=a/b+48;
}
return c;
}
// 算法3.4 P54
// 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈
SElemType EvaluateExpression()
{
SqStack OPTR,OPND;
SElemType a,b,c,x,theta;
InitStack(OPTR);
Push(OPTR,'#');
InitStack(OPND);
c=getchar();
GetTop(OPTR,x);
while(c!='#'||x!='#')
{
if(In(c)) // 是7种运算符之一
switch(Precede(x,c))
{
case'<':
Push(OPTR,c); // 栈顶元素优先权低
c=getchar();
break;
case'=':
Pop(OPTR,x); // 脱括号并接收下一字符
c=getchar();
break;
case'>':
Pop(OPTR,theta); // 退栈并将运算结果入栈
Pop(OPND,b);
Pop(OPND,a);
Push(OPND,Operate(a,theta,b));
break;
}
else if(c>='0'c<='9') // c是操作数
{
Push(OPND,c);
c=getchar();
}
else // c是非法字符
{
printf("非法字符\n");
exit(0);
}
GetTop(OPTR,x);
}
GetTop(OPND,x);
return x;
}
int main()
{
printf("请输入算术表达式（中间值及最终结果要在0～9之间），"
"并以#结束\n");
printf("例如：3*(7-5)#\n");
printf("%c\n",EvaluateExpression());
system("pause");
return 0;
}
/*
输出效果：
请输入算术表达式（中间值及最终结果要在0～9之间），并以#结束
例如：3*(7-5)#
3*(7-5)#
6
请按任意键继续. . .
请输入算术表达式（中间值及最终结果要在0～9之间），并以#结束
例如：3*(7-5)#
4+2*3-10/5#
8
请按任意键继续. . .
*/
2. 算数表达式求值c++
为了简化问题，关注算法，本文的讨论基于以下三点：
1. 只考虑 + - * / ( ) 这几个基本运算符，且是二元操作
2. 运算数只考虑 0-9，这10个简单的数，方便从string中取出来
3. 输入的表达式没有语法错误
【背景知识】
中缀表示法（Infix expression）：操作符位于两个操作数中间，算术表达式的常规表示法。只用于二元操作符的情况，而且需要用括号和优先规则排除多义性。(A+B)*C-D/(E+F)
前缀表示法（Prefix expression）：也叫波兰表示法，操作符写在操作数的前面。这种方法常用于编译器设计方面。-*+ABC/D+EF
后缀表示法（Postfix expression），逆波兰表示法，操作符位于操作数后面。这种方法使表达式求值很方便。AB+C*DEF+/-
前、后缀表示法的三个特征：
1. 操作数的顺序与等价的中缀表示法中操作数的顺序一致
2. 不需要括号
3. 操作符的优先级不相关
用二叉树来表示更直观，前、中、后缀表示法分别对应前序、中序、后序遍历得到的结果。
【算符优先法】
输入中缀表达式，直接求值。首先了解四则运算的规则：
（1） 先乘除，后加减
（2） 从左到右
（3） 先括号内，后括号外
根据以上3条规则，在运算的每一步，任意两个相继出现的算符optr1和optr2之间的优先关系有3种：
>：optr1的优先权高于optr2
=：optr1的优先权等于optr2
<：optr1的优先权低于optr2
下表定义了算符之间的优先级。竖：optr1，横：optr2。
+
-
*
/
(
)
#
+
>
>
<
<
<
>
>
-
>
>
<
<
<
>
>
*
>
>
>
>
<
>
>
/
>
>
>
>
<
>
>
(
<
<
<
<
<
=
)
>
>
>
>
>
>
#
<
<
<
<
<
=
在表达式的两头，分别加个#符号，当##配对时，代表求值完成。
由规则（1），+ - 比* / 的优先权低；由规则（2），当optr1=optr2时，令optr1 > optr2；由规则（3），optr1为+ - * / 时的优先级低于 ( 高于 ) ，当optr1为 ( 时，优先级最低，optr1为 ) 时，优先级最高。
算法实现：使用两个栈，分别存放操作符和操作数。
1）置操作数栈为空，起始符#入运算符栈。
2）依次读入表达式中的每个字符，如是操作数，入操作数栈；如是运算符，和运算符栈顶符号比较优先权。直到表达式求值完毕，即##配对。
[cpp]view plain
boolIsOperator(charch)
{
if(ch=='+'||ch=='-'||
ch=='*'||ch=='/'||
ch=='('||ch==')'||ch=='#')
returntrue;
else
returnfalse;
}
//运算符的优先关系
//'+','-','*','/','(',')','#'
charOprRelation[7][7]={{'>','>','<','<','<','>','>'},//'+'
{'>','>','<','<','<','>','>'},//'-'
{'>','>','>','>','<','>','>'},//'*'
{'>','>','>','>','<','>','>'},//'/'
{'<','<','<','<','<','=',''},//'('
{'>','>','>','>','','>','>'},//')'
{'<','<','<','<','<','','='}};//'#'
intConvertToIndex(charopr)
{
intindex;
switch(opr)
{
case'+':
index=0;
break;
case'-':
index=1;
break;
case'*':
index=2;
break;
case'/':
index=3;
break;
case'(':
index=4;
break;
case')':
index=5;
break;
case'#':
index=6;
break;
}
returnindex;
}
charPrecede(charopr1,charopr2)
{
intindex1=ConvertToIndex(opr1);
intindex2=ConvertToIndex(opr2);
returnOprRelation[index1][index2];
}
intOperate(intopnd1,charop,intopnd2)
{
intret;
switch(op)
{
case'+':
ret=opnd1+opnd2;
break;
case'-':
ret=opnd1-opnd2;
break;
case'*':
ret=opnd1*opnd2;
break;
case'/':
ret=opnd1/opnd2;
break;
}
returnret;
}
//算符优先算法
intCaculateExpression(stringexp)
{
stack<char>optr;//只处理+-#/()运算
stack<int>opnd;//只处理0-9的整数运算
charch;
inti=0;
exp+="#";
optr.push('#');
ch=exp[i++];
//如果##配对，表达式求值完成
while(ch!='#'||optr.top()!='#')
{
if(!IsOperator(ch))
{
//操作数入栈
opnd.push(ch-'0');
ch=exp[i++];
}
else
{
//比较栈顶操作符和新取得的操作符的优先关系
switch(Precede(optr.top(),ch))
{
case'<'://栈顶优先权低
optr.push(ch);
ch=exp[i++];
break;
case'='://括号配对，栈顶括号弹出
optr.pop();
ch=exp[i++];
break;
case'>'://栈顶优先权高，先弹出，计算，结果操作数入栈
charop=optr.top();
optr.pop();
intnum2=opnd.top();//第二个操作数在前
opnd.pop();
intnum1=opnd.top();
opnd.pop();
intret=Operate(num1,op,num2);
opnd.push(ret);
break;
}
}
}//endofwhile
//操作数栈的唯一元素即为计算结果
returnopnd.top();
}
boolPrior(charoptr1,charoptr2)
{
boolprior=false;
if(optr1=='*'||optr1=='/')
if(optr2=='+'||optr2=='-')
prior=true;
returnprior;
}
//前缀表达式->后缀表达式
stringPrefixToPostFix(stringexp)
{
stringpostRet;
stack<char>optr;
inti=0;
charch;
while(i<exp.length())
{
ch=exp[i++];
if(IsOperator(ch))
{
switch(ch)
{
case'(':
optr.push(ch);
break;
case')':
//将栈中最近的一个左括号之上的操作符全部弹出，添加到结果
while(optr.top()!='(')
{
postRet+=optr.top();
optr.pop();
}
optr.pop();//丢弃左括号
break;
case'+':
case'-':
case'*':
case'/':
//弹出操作符，直到栈为空，或遇到左括号，或优先级较低的操作符
//或者统一优先级的右结合操作符
while(!optr.empty()&&Prior(optr.top(),ch))
{
postRet+=optr.top();
optr.pop();
}
optr.push(ch);
break;
}
}
else
{
postRet+=ch;
}
}
//到达字符串末尾，弹出所有操作符，添加到结果
while(!optr.empty())
{
postRet+=optr.top();
optr.pop();
}
returnpostRet;
}
//前缀表达式->后缀表达式，再求值
intCaculateExpression_2(stringpostExp)
{
//先转换成后缀表达式
stringexp=PrefixToPostFix(postExp);
stack<int>opnd;
inti=0;
charch;
while(i<exp.length())
{
ch=exp[i++];
if(IsOperator(ch))
{
intnum2=opnd.top();
opnd.pop();
intnum1=opnd.top();
opnd.pop();
//计算结果并入栈
intret=Operate(num1,ch,num2);
opnd.push(ret);
}
else
{
//操作数入栈
opnd.push(ch-'0');
}
}
returnopnd.top();
}
【前缀->后缀表达式】
1）操作符栈为空，结果字符串为空。
2）依次读入中缀表达式的每个字符
-如是操作数，添加到结果字符串
-如是左括号，入操作符栈
-如是右括号，弹出栈内符号，添加到结果字符串，直到遇到栈内的左括号。弹出左括号。
-如是操作符，弹出栈内符号，添加懂啊结果字符串，直到遇到左括号，或优先级较低的操作符，或统一优先级的右结合符号。此操作符入栈
3）如到达字符串末尾，弹出所有栈内符号，添加到结果字符串
[cpp]view plain
【后缀表达式求值】
1）初始化操作数栈
2）从左到右依次读入后缀表达式的每个字符，如是操作数，入栈；如是操作符，弹出两个操作数，计算，结果入栈，直到表达式末尾。栈中的唯一数即是结果。注意弹出的第一个操作数是位于运算符右边的数。
[cpp]view plain
【二叉树法】
可以根据前缀表达式，构造出二叉树，后序遍历即得到后缀表达式。
【手动方法】
(A+B)*C-D/(E+F)
1）按照运算符优先级对所有运算单位加括号。(((A+B)*C）-(D/(E+F)))
2）前缀：把运算符移动到对应的括号前面：-(*(+(AB)C)/(D+(EF)))，再去掉括号：-*+ABC/D+EF
3）后缀：把运算符移动到对应的括号后面：(((AB)+C)*(D(EF)+)/)-，再去掉括号：AB+C*DEF+/-
3. 算术表达式求值算法
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<string.h>
#define DEBUG
#define NULL 0
#define ERROR -1
#define STACKSIZE 20
/* 定义字符类型栈 */
typedef struct{
char stackname[20];
char *base;
char *top;
} Stack;
/* ----------------- 全局变量--------------- */
Stack OPTR, OPND; /* 定义前个运算符栈，后个操作数栈 */
char expr[255] = ""; /* 存放表达式串 */
char *ptr = expr;
int step = 0; /* 计算的步次 */
int InitStack(Stack *s, char *name)
{
s->base=(char *)malloc(STACKSIZE*sizeof(char));
if(!s->base) exit (ERROR);
strcpy(s->stackname, name);
s->top=s->base;
return 1;
}
int In(char ch)
{
return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#');
}
void OutputStatus(void)
{
char *s;
/* step */
printf("\n%-8d", ++step);
/* OPTR */
for(s = OPTR.base; s < OPTR.top; s++)
printf("%c", *s);
printf("\t");
/* OPND */
for(s = OPND.base; s < OPND.top; s++)
printf("%d ", *s);
/* input char */
printf("\t\t%c", *ptr);
}
int Push(Stack *s,char ch)
{
#ifdef DEBUG
char *name = s->stackname;
OutputStatus();
if(strcmp(name, "OPND") == 0)
printf("\tPUSH(%s, %d)", name, ch);
else
printf("\tPUSH(%s, %c)", name, ch);
#endif
*s->top=ch;
s->top++;
return 0;
}
char Pop(Stack *s)
{
char p;
#ifdef DEBUG
OutputStatus();
printf("\tPOP(%s)", s->stackname);
#endif
s->top--;
p=*s->top;
return (p);
}
char GetTop(Stack s)
{
char p=*(s.top-1);
return (p);
}
/* 判断运算符优先权，返回优行权高的 */
char Precede(char c1,char c2)
{
int i=0,j=0;
static char array[49]={ '>', '>', '<', '<', '<', '>', '>',
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'<', '<', '<', '<', '<', '=', '!',
'>', '>', '>', '>', '!', '>', '>',
'<', '<', '<', '<', '<', '!', '='};
switch(c1)
{
/* i为下面array的横标 */
case '+' : i=0;break;
case '-' : i=1;break;
case '*' : i=2;break;
case '/' : i=3;break;
case '(' : i=4;break;
case ')' : i=5;break;
case '#' : i=6;break;
}
switch(c2)
{
/* j为下面array的纵标 */
case '+' : j=0;break;
case '-' : j=1;break;
case '*' : j=2;break;
case '/' : j=3;break;
case '(' : j=4;break;
case ')' : j=5;break;
case '#' : j=6;break;
}
return (array[7*i+j]); /* 返回运算符 */
}
/*操作函数 */
int Operate(int a,char op,int b)
{
#ifdef DEBUG
OutputStatus();
printf("\tOPERATE(%d, %c, %d)", a, op, b);
#endif
switch(op)
{
case '+' : return (a+b);
case '-' : return (a-b);
case '*' : return (a*b);
case '/' : return (a/b);
}
return 0;
}
int EvalExpr(void)
{
char c,theta,x,m,ch;
int a,b;
c = *ptr++;
while(c!='#'||GetTop(OPTR)!='#')
if(!In(c))
{
m=atoi(&c);
Push(&OPND,m);
c = *ptr++;
}
else
switch(Precede(GetTop(OPTR),c))
{
case '<':
Push(&OPTR,c);
c = *ptr++;
break;
case '=':
x=Pop(&OPTR);
c = *ptr++;
break;
case '>':
theta=Pop(&OPTR);
b=Pop(&OPND); a=Pop(&OPND);
Push(&OPND,Operate(a,theta,b));
break;
}
return GetTop(OPND);
}
int main(void)
{
/*
printf("Input the expression(end with \"#\" sign):");
do{
gets(expr);
}while(!*expr); */
//strcpy(expr, "2*(2+3)#");
char *pc;
printf("Input the expression(end with \"#\" sign):");
gets(expr);
pc=expr;
if(expr[0]=='\0')
{
printf("Please input a valid expression!\n");
printf("Input the expression again(end with \"#\" sign):");
gets(expr);
}
else
{
while(*pc!='\0')
pc++;
pc--;
if(*pc!='#')
{
printf("Please asure the expression end with \"#\" sign!\n");
printf("Input the expression again(end with \"#\" sign):");
gets(expr);
}
}
InitStack(&OPTR, "OPTR"); /* 初始化运算符栈 */
Push(&OPTR,'#'); /* 将#压入运算符栈 */
InitStack(&OPND, "OPND"); /* 初始化操作数栈 */
printf("\n\nresult:%d\n", EvalExpr());
system("pause");
return 0;
}
4. 急！算数表达式求值的优先算法！
定义：运算符栈S，操作数栈C
读3+，+压入栈S，3压入栈C；
读5*7，*压入栈S，5压入栈C，7压入栈C；
读-，*运算顺序高于+-，取栈C中的7和5，取栈S中的*，计算5*7=35，35压入栈C，-压入栈S；
读4，压入栈C，读取完；
取栈C中的4和35，取栈S中的-，计算35-4=31，取栈C中的3，取栈S中的+，计算3+31=34
5. 数据结构写程序实现表达式求值算法
这是c++的代码
0stdafx.h
//stdafx.h:标准系统包含文件的包含文件，
//或是经常使用但不常更改的
//特定于项目的包含文件
//
//#pragmaonce是一个比较常用的C/C++杂注，只要在头文件的最开始加入这条杂注，就能够保证头文件只被编译一次。
#pragmaonce
#include"targetver.h"
#include<stdio.h>
#include<tchar.h>
#include<iostream>
#include<stdlib.h>
#include<string>
#include<string.h>
#include<math.h>
#include<time.h>
usingnamespacestd;
//TODO:在此处引用程序需要的其他头文件
1 stack栈的结构
#pragmaonce
#include"stdafx.h"
#include"StackNode.h"
//LinkStack,链式栈的类定义
template<typenameT>
classStack{
private:
StackNode<T>*top;//curptr
//7个方法
public:
//ConstructFunction()
Stack():top(NULL){}
//DeConstructFunction()
~Stack(){
StackNode<T>*p;//temprefdomain
while(top!=NULL){//free()
p=top;
top=top->next;
deletep;
}
}
//Push()从栈顶压入一个元素
voidPush(constT&item){
StackNode<T>*p=newStackNode<T>;
p->data=item;//赋值
p->next=top;//connectcurptr
top=p;//curptrmove++
}
//Pop()从栈顶弹出一个元素
TPop(){
if(IsEmpty()){//emptystack
cerr<<"Attempttopopanemptystack!"<<endl;
exit(1);
}
StackNode<T>*p=top;//temprefdomain
TRetValue=p->data;//tempdatadomain
top=top->next;//top--move
deletep;//free()p,elsewillcrashmemory
returnRetValue;
}
//Peek(),GetTop()
TPeek()const{
if(IsEmpty()){//emptystack
cerr<<"Attempttopopanemptystack!"<<endl;
exit(1);
}
returntop->data;
}//!_Peek
//Clear()
voidClear(void){
//不free()会内存泄漏
StackNode<T>*p;//temprefdomain
while(top!=NULL){//free()
p=top;
top=top->next;
deletep;
}
this.top=NULL;
}//!_Clear()
//IsEmpty()
intIsEmpty(void)const{
returntop==NULL;
}//!_IsEmpty()
};//!_classStack
2表达式求值算法
#pragmaonce
#include"stdafx.h"
#include"Stack.h"
//方法的声明实现的分离写法容易报错，IDE还找不到错误的地方
//表达式求值
classCalculator{
private:
//Calculator'sstack,运算存储区
Stack<double>s;
//7个方法
public:
//建立一个空计算器栈
Calculator(void){}
//De建立一个空计算器栈
virtual~Calculator(){}
//将一个double型操作数压入堆栈
voidEnter(doubleoperand){
s.Push(operand);
}
//弹出2个操作数
voidGetTwoOperands(double&operand1,double&operand2){
if(s.IsEmpty()){
cerr<<"Nooperandtobepop!"<<endl;
s.Clear();
exit(1);
}
operand1=s.Pop();
if(s.IsEmpty){
cerr<<"Nooperandtobepop!"<<endl;
s.Clear();
exit(1);
}
operand2=s.Pop();
}
//操作符运算
voidCompute(charop){
doubleoperand1,operand2,result;
GetTwoOperands(operand1,operand2);
switch(op){
case'+':result=operand1+operand2;break;
case'-':result=operand1-operand2;break;
case'*':result=operand1*operand2;break;
case'/':if(operand2==0){
cerr<<"Dividedby0!"<<endl;
s.Clear();
exit(1);
}else
result=operand1/operand2;break;
default:
break;
}
s.Push(result);
}
//清空栈
voidClear(){
s.Clear();
}
//计算表达式的值
voidRun(){
charop;//操作符
doubleoperand;//操作数
cin>>op;//输入操作符
while(op!='='){
switch(op){
case'+':case'-':case'*':case'/':
Compute(op);break; //运算
default:cin.putback(op);//非操作符，回流
cin>>operand;//入操作数
Enter(operand);break;//入栈操作数
}
cin>>op;//输入操作符
}
cout<<s.Pop()<<endl;//最后出栈
Clear();//清空栈
}
};//!_classCalculator
6. 数据结构设计~《表达式求值》！
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
typedef struct {
char *base;
char *top;
int stacksize;
} stack; //字符栈
int InitStack(stack *s) { //初始化栈
s->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
if (!s->base) {
exit(1);
} else {
s->top = s->base;
s->stacksize = STACK_INIT_SIZE;
}
}
char GetTop(stack *s) { //用e返回栈顶元素
if (s->base == s->top) {
printf("栈已空\n");
} else {
return(*(s->top - 1));
}
}
void Pop(stack *s, char *e) { //返回栈顶元素，注意此处e的值需要改变，因该使用指针
if (s->base == s->top) {
printf("栈已空\n");
} else {
*e = *--s->top;
}
}
int Push(stack *s, char e) { //将e入栈
if (s->top - s->base >= s->stacksize) {
s->base = (char *)realloc(s->base, (s->stacksize + STACK_INCREMENT) * sizeof(char));
if (!s->base) {
exit(1);
} else {
s->top = s->base + s->stacksize;
s->stacksize += STACK_INCREMENT;
}
} else {
*s->top++ = e;
}
}
char JudgePrecede(char symbol1, char symbol2) {
//优先级判断算法
char pre[7][7] = {{'>', '>', '<', '<', '<', '>', '>'}, //运算符优先级设置有二维数组完成
{'>', '>', '<', '<', '<', '>', '>'},
{'>', '>', '>', '>', '<', '>', '>'},
{'>', '>', '>', '>', '<', '>', '>'},
{'<', '<', '<', '<', '<', '=', ' '},
{'>', '>', '>', '>', ' ', '>', '>'},
{'<', '<', '<', '<', '<', ' ', '='}
} ;
int row, line;
switch (symbol1) {
case '+':
row = 0;
break;
case '-':
row = 1;
break;
case '*':
row = 2;
break;
case '/':
row = 3;
break;
case '(':
row = 4;
break;
case ')':
row = 5;
break;
case '#':
row = 6;
break;
default:
break;
}
switch (symbol2) {
case '+':
line = 0;
break;
case '-':
line = 1;
break;
case '*':
line = 2;
break;
case '/':
line = 3;
break;
case '(':
line = 4;
break;
case ')':
line = 5;
break;
case '#':
line = 6;
break;
default:
break;
}
return(pre[row][line]);
}
int IfOperator(char c) {
//判断c是否为运算符
if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')' || c == '#') {
return(1);
} else {
return(0);
}
}
char Operation(char operand1, char operator, char operand2) {
//四则运算
switch (operator) {
case '+':
return(operand1 + operand2 - '0'); //0的ASC2为048
break;
case '-':
return(operand1 - operand2 + '0');
break;
case '*':
return((operand1 - '0') * (operand2 - '0') + '0');
break;
case '/':
return((operand1 - '0') / (operand2 - '0') + '0');
break;
default:
break;
}
}
void EvaluateExpression(char *e) {
//算法描述，以＃结尾，用e返回表达式的值
stack OPND; //OPTR为运算符栈，OPND为操作数栈
stack OPTR;
InitStack(&OPTR);
InitStack(&OPND);
Push(&OPTR, '#');
char operator, a, b, c;
c = getchar();
while (c != '#' || GetTop(&OPTR) != '#') {
if (!IfOperator(c)) {
Push(&OPND, c);
c = getchar();
} else {
switch (JudgePrecede(GetTop(&OPTR), c)) {
case '<':
Push(&OPTR, c);
c = getchar();
break;
case '=':
Pop(&OPTR, &operator);
c = getchar();
break;
case '>':
Pop(&OPTR, &operator);
Pop(&OPND, &b);
Pop(&OPND, &a);
Push(&OPND, Operation(a, operator, b));
break;
default:
break;
}
}
}
*e = GetTop(&OPND);
}
main(){
printf("输入一条表达式,以'#'结尾,回车\n");
char e;
EvaluateExpression(&e);
printf("%d\n", e - '0');
system("pause");
}
7. C语言表达式求值
//表达式求值
//By:jimly
//10/10/2009
//例如：输入2+2（4-6*3）=
//以"="结束,然后回车即出结果
#include <stdio.h>
#include <conio.h>
#include <windows.h>
#include <assert.h>
typedef float ElemType;
typedef struct Stack
{
ElemType *base; // 栈基址
ElemType *top; // 栈顶
int stacksize; // 栈存储空间的尺寸
} SqStack;
/*------------------------------------------------------------
// 栈的基本操作
------------------------------------------------------------*/
bool InitStack(SqStack *S);
bool InitStack(SqStack *S);
void DestroyStack(SqStack *S);
bool StackEmpty(SqStack S);
int StackLength(SqStack S);
ElemType GetTop(SqStack S, ElemType *e);
void StackTraverse(SqStack S, void (*fp)(ElemType));
bool Push(SqStack *S, ElemType e);
bool Pop(SqStack *S, ElemType *e);
/*------------------------------------------------------------
// 表达式求值的操作函数定义
------------------------------------------------------------*/
char Precede(char A1,char A2);
ElemType Operate(ElemType a,ElemType theta,ElemType b);
bool In(char c,char op[]);
ElemType EvaluateExpression();
void Menu();//////////////////////////////////////////////
// Eval_exdivssion.cpp 表达式求值实现函数 //
//////////////////////////////////////////////
/*------------------------------------------------------------
操作目的： 判定运算符栈的栈顶运算符A1和读入的运算符A2之间优先关系的函数
初始条件： 无
操作结果： 判断出优先关系
函数参数：
char A1 运算符
char A2 运算符
返回值：
char 大小关系
------------------------------------------------------------*/
char Precede(char A1,char A2)
{
if (A1 == '+' || A1 == '-')
{
if (A2 == '+' || A2 == '-' || A2 == ')' || A2 == '=')
{
return '>';
}
else
return '<';
}
if (A1 == '*' || A1 == '/')
{
if (A2 == '(')
{
return '<';
}
else
return '>';
}
if (A1 == '(')
{
if (A2 == ')')
{
return '=';
}
if (A2 == '=')
{
return 'E';
}
else
return '<';
}
if (A1 == ')')
{
if (A2 == '(')
{
return 'E';
}
if (A2 == '=')
{
return 'E';
}
else
return '>';
}
if (A1 == '=')
{
if (A2 == '=')
{
return '=';
}
else
return '<';
}
else
return '=';
}
/*------------------------------------------------------------
操作目的： 二元运算a与b的函数
初始条件： 无
操作结果： 返回运算结果
函数参数：
ElemType a 操作数
ElemType theta 操作符
ElemType b 操作数
返回值：
ElemType 运算结果
------------------------------------------------------------*/
ElemType Operate(ElemType a,ElemType theta,ElemType b)
{
switch(char(theta))
{
case '+':
return a += b;
break;
case '-':
return a -= b;
break;
case '*':
return a *= b;
break;
case '/':
if(b==0)
{
printf("除数不能为0！！\n");
exit(0);
}
return a /= b;
break;
} return 0;
}
/*------------------------------------------------------------
操作目的： 判断字符c是否属于运算符集合op
初始条件： 无
操作结果： 返回判断结果
函数参数：
char c 要判断的字符
char op[] 运算符集合
返回值：
bool 属于返回true 否则返回false
------------------------------------------------------------*/
bool In(char c,char op[])
{
for (int i = 0;i<7;i++)
{
if (op[i] == c)
return true;
}
return false;
}
/*------------------------------------------------------------
操作目的： 算术表达式求值的运算符优先算法
初始条件： 无
操作结果： 返回表达式的值
函数参数：
无
返回值：
ElemType 运算结果
------------------------------------------------------------*/
ElemType EvaluateExpression()
{
SqStack OPTR; //运算符栈
SqStack OPND; //运算数栈
char Ct = '='; //判断是否结束的标识
int i = 0,j = 1;
ElemType e = 0,t = 0,c;
char op[7] = {'+','-','*','/','(',')','='}; InitStack(&OPTR); //初始化
Push(&OPTR,Ct);
InitStack(&OPND); //初始化 c = (float)getchar();
while (c!='=' || GetTop(OPTR,&e)!='=')
{
if (!In((char)c,op)) //不是运算e符进栈
{
while(!In((char)c,op)) //可以是几位数
{
t = t*10+(c-48);
c = (float)getchar();
}
Push(&OPND,t);
t = 0;
} else
{
switch (Precede((char)GetTop(OPTR,&e),(char)c))
{
case '<'://栈顶元素优先权低
Push(&OPTR,c);
c = (float)getchar();
break;
case '='://脱括号并接受下个字符
ElemType x;
Pop(&OPTR,&x);
c = (float)getchar();
break;
case '>'://退栈并将运算结果入栈
ElemType b,theta,a;
Pop(&OPTR,&theta);
Pop(&OPND,&b);
Pop(&OPND,&a);
Push(&OPND,Operate(a,theta,b));
break;
case 'E':
printf("括号不匹配！！\n");
exit(0);
break;
}
}
}
ElemType tem = GetTop(OPND,&e);
DestroyStack(&OPND);
DestroyStack(&OPTR);
return tem;
}/***
*DynaSeqStack.cpp - 动态顺序栈，即栈的动态顺序存储实现
****/
const int STACK_INIT_SIZE = 100; // 初始分配的长度
const int STACKINCREMENT = 10; // 分配内存的增量
/*------------------------------------------------------------
操作目的： 初始化栈
初始条件： 无
操作结果： 构造一个空的栈
函数参数：
SqStack *S 待初始化的栈
返回值：
bool 操作是否成功
------------------------------------------------------------*/
bool InitStack(SqStack *S)
{
assert(S != NULL);
S->base = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);
if(S->base == NULL) return false; S->top = S->base;
S->stacksize = STACK_INIT_SIZE; return true;
}/*------------------------------------------------------------
操作目的： 销毁栈
初始条件： 栈S已存在
操作结果： 销毁栈S
函数参数：
SqStack *S 待销毁的栈
返回值：
无
------------------------------------------------------------*/
void DestroyStack(SqStack *S)
{
assert(S != NULL); free(S->base);
S->top = S->base = NULL;
}/*------------------------------------------------------------
操作目的： 判断栈是否为空
初始条件： 栈S已存在
操作结果： 若S为空栈，则返回true，否则返回false
函数参数：
SqStack S 待判断的栈
返回值：
bool 是否为空
------------------------------------------------------------*/
bool StackEmpty(SqStack S)
{
assert((S.base != NULL) && (S.top != NULL));
return(S.base == S.top);
}/*------------------------------------------------------------
操作目的： 得到栈的长度
初始条件： 栈S已存在
操作结果： 返回S中数据元素的个数
函数参数：
SqStack S 栈S
返回值：
int 数据元素的个数
------------------------------------------------------------*/
int StackLength(SqStack S)
{
assert((S.base != NULL) && (S.top != NULL));
return(S.top-S.base);
}/*------------------------------------------------------------
操作目的： 得到栈顶元素
初始条件： 栈S已存在
操作结果： 用e返回栈顶元素
函数参数：
SqStack S 栈S
ElemType *e 栈顶元素的值
返回值：
bool 操作是否成功
------------------------------------------------------------*/
ElemType GetTop(SqStack S, ElemType *e)
{
assert((S.base != NULL) && (S.top != NULL));
if(StackEmpty(S)) return false; *e = *(S.top-1);
return *e;
}/*------------------------------------------------------------
操作目的： 遍历栈
初始条件： 栈S已存在
操作结果： 依次对S的每个元素调用函数fp
函数参数：
SqStack S 栈S
void (*fp)() 访问每个数据元素的函数指针
返回值：
无
------------------------------------------------------------*/
void StackTraverse(SqStack S, void (*fp)(ElemType))
{
assert((S.base != NULL) && (S.top != NULL));
for(; S.base<S.top; S.base++) (*fp)(*S.base);
}/*------------------------------------------------------------
操作目的： 压栈——插入元素e为新的栈顶元素
初始条件： 栈S已存在
操作结果： 插入数据元素e作为新的栈顶
函数参数：
SqStack *S 栈S
ElemType e 待插入的数据元素
返回值：
bool 操作是否成功
------------------------------------------------------------*/
bool Push(SqStack *S, ElemType e)
{
if (S->top - S->base>=S->stacksize)
{
S->base = (ElemType *)realloc(S->base,(S->stacksize + STACKINCREMENT) * sizeof(ElemType));
if (!S->base)
exit(0);
S->top = S->base + S->stacksize;
S->stacksize += STACKINCREMENT;
}
*S->top++ = e; return true;
}/*------------------------------------------------------------
操作目的： 弹栈——删除栈顶元素
初始条件： 栈S已存在且非空
操作结果： 删除S的栈顶元素，并用e返回其值
函数参数：
SqStack *S 栈S
ElemType *e 被删除的数据元素值
返回值：
bool 操作是否成功
------------------------------------------------------------*/
bool Pop(SqStack *S, ElemType *e)
{
if(S == NULL) return false;
assert((S->base != NULL) && (S->top != NULL));
if(StackEmpty(*S)) return false; *e = *(--S->top);
return true;
}//////菜单///////
void Menu()
{
printf("表达式求值模拟程序\n\n");
printf("功能菜单：\n");
printf("==============\n");
printf("[1] 输入表达式并求值\n");
printf("[0] 退出 \n");
printf("==============\n");
printf("请输入你的选择(0~1)（以回车结束）：");
}///////// 主函数 ///////////
//////////////////////////////
int main()
{
char ch = ' ',tp; do
{
system("cls");
Menu();
ch = getchar();
if (ch == '0')
break;
tp = getchar();
printf("请输入一个表达式（最后输入”=“,然后回车出结果）：");
printf("这个表达式结果为：%g\n",EvaluateExpression());
tp = getchar();
printf("任意键继续...");
getch();
} while (true); return 0;
}//end
8. 表达式求值
从算法来说，要考虑中缀的运算符优先级，括号等，可以使用简单语法制导翻译，去看编译原理书吧，从数据结构来说，可以使用二元树和栈。使用二元树就是先建立表达式的树，然后后根遍历即可。难点在建立树。
使用栈的算法也很多，说个好想的。假设表达式的字符来自输入流in，建立栈A存放运算符，B存放结果，从in读入一个操作数压进B，读入一个运算符压进A，如此反复。
1.读入一个元素e
2.如果e是操作数或者(，压入B，跳转到1
3.如果e是运算符(不包含括号)，跳转到3.1
4.如果e是)，跳转到4.1
5.如果e是EOF，即输入流结束，反复弹出A栈顶压入B，直到A为空，算法结束，B从栈底到栈顶的符号即为后缀表达式（需要把B翻个个儿^_^）
3.1.判断A的栈定符号t，如果t不为(，且优先级大于等于e，则弹出t压入B，跳转到4，如果t为空，即栈中为空，或其他情况直接把e压入A，跳转到1
4.1.弹出A的栈顶压入到B，如此反复直到弹出的符号为(,(和)不要压入B,跳转到1
这是我临时想的，可能还有bug，或描述不清的地方，如果上网搜的话应该有很多源代码的，如果学过编译原理的话还可以有更好的算法，这个算法没考虑容错性。