表達式求值演算法
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，或描述不清的地方，如果上網搜的話應該有很多源代碼的，如果學過編譯原理的話還可以有更好的演算法，這個演算法沒考慮容錯性。