表達(dá)式求值
這里介紹一種簡(jiǎn)單直觀的“算符優(yōu)先法”。
要對(duì)一個(gè)表達(dá)式求值葫掉，首先要能夠正確解釋表達(dá)式稍刀。
例如表悬，要求對(duì)下面的算術(shù)表達(dá)式求值：
4+2*3-10/5
首先要了解算術(shù)四則運(yùn)算的規(guī)則。即：
(1)先乘除沼侣，后加減
(2)從左算到右
(3)先括號(hào)內(nèi)祖能，后括號(hào)外。
由此蛾洛，這個(gè)算術(shù)表達(dá)式的計(jì)算順序應(yīng)為：
4 + 2 * 3 - 10 / 5 = 4 + 6 - 10 / 5 = 10 - 10 / 5 = 10 - 2 =8
算符優(yōu)先法就是根據(jù)這個(gè)運(yùn)算關(guān)系的規(guī)定來(lái)實(shí)現(xiàn)對(duì)表達(dá)式的編譯或解釋執(zhí)行的养铸。
任何一個(gè)表達(dá)式都是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的轧膘。
一般的钞螟，操作數(shù)既可以是常數(shù)也可以是被說(shuō)明為變量或常量的標(biāo)識(shí)符；
運(yùn)算符可以分為算術(shù)運(yùn)算符谎碍、關(guān)系運(yùn)算符和邏輯運(yùn)算符3類(lèi)鳞滨；
基本界限符有左右括號(hào)和表達(dá)式結(jié)束符等。
我們把運(yùn)算符和界限符統(tǒng)稱(chēng)為算符蟆淀，他們構(gòu)成的集合命名為OP拯啦。根據(jù)上述3條運(yùn)算規(guī)則，在運(yùn)算的每一步中熔任，任意兩個(gè)相繼出現(xiàn)的算符a和b之間的優(yōu)先關(guān)系至多是下面三種關(guān)系之一：
a<b：a的優(yōu)先級(jí)低于b
a=b：a的優(yōu)先級(jí)等于b
a>b：a的優(yōu)先級(jí)大于b
下表給出了部分a褒链、b運(yùn)算符之間的優(yōu)先級(jí)關(guān)系（列為a運(yùn)算符，行為b運(yùn)算符）：
| + | - | * | / | % | ( | ) | |
|---|---|---|---|---|---|---|---|
| + | > | > | < | < | < | < | > |
| - | > | > | < | < | < | < | > |
| * | > | > | > | > | > | < | > |
| / | > | > | > | > | > | < | > |
| % | > | > | > | > | > | < | > |
| ( | < | < | < | < | < | < | = |
| ) | > | > | > | > | > | N | N |
表達(dá)式中的‘=’表示當(dāng)左右括號(hào)相遇時(shí)笋敞，括號(hào)內(nèi)的運(yùn)算完成碱蒙，此時(shí)要把左右括號(hào)從表達(dá)式中及時(shí)脫離。
表達(dá)式中的'N'表示這種狀態(tài)如果出現(xiàn)了夯巷，則表達(dá)式格式有誤赛惩，一定是左右括號(hào)不匹配。
在代碼中趁餐，我給出了上述7種運(yùn)算符
char opetr_char[7]={'+','-','*','/','%','(',')'};
首先是要判斷一個(gè)字符屬不屬于運(yùn)算符喷兼，
int isOpetrChar(char ch){
int i;
for(i=0;i<7;i++){
if(ch == opetr_char[i]) return i;
}
return -1;
}
上表的優(yōu)先級(jí)用一個(gè)char型的二維數(shù)組直觀表示：
char opetr_priority[7][7]={
{'>','>','<','<','<','<','>'},
{'>','>','<','<','<','<','>'},
{'>','>','>','>','>','<','>'},
{'>','>','>','>','>','<','>'},
{'>','>','>','>','>','<','>'},
{'<','<','<','<','<','<','='},
{'>','>','>','>','>','N','N'}
};
那么，比較兩個(gè)運(yùn)算符的優(yōu)先級(jí)可以簡(jiǎn)單得出：
char getOpetrPrior(char a,char b){
int i = isOpetrChar(a);
int j = isOpetrChar(b);
return opetr_priority[i][j];
}
實(shí)現(xiàn)算符優(yōu)先算法后雷，可以使用兩個(gè)棧季惯，一個(gè)optr_stack吠各，用于存放運(yùn)算符，一個(gè)opnd_stack勉抓，用于存放操作數(shù)贾漏。
算法的核心思想是，依次讀入表達(dá)式中每個(gè)字符藕筋，若是操作數(shù)則進(jìn)opnd_stack纵散，若是運(yùn)算符則與optr_stack的棧頂操作符比較優(yōu)先權(quán)后作相應(yīng)操作，直至整個(gè)表達(dá)式求值完畢隐圾。
EvaluateExpression.c利用了前面的C封裝的順序棧對(duì)象 用線性表表示的順序棧
實(shí)現(xiàn)了輸入表達(dá)式伍掀，顯示每一步的計(jì)算過(guò)程，并輸出最終結(jié)果的功能暇藏。
且支持表達(dá)式格式檢測(cè)蜜笤，支持多重括號(hào)結(jié)構(gòu)、負(fù)數(shù)運(yùn)算（‘-’號(hào)既可能為減號(hào)盐碱，也可能為負(fù)號(hào)）把兔。
EvaluateExpression.c文件
#include <stdio.h>
#include <malloc.h>
#include "LinearListStack.h"
char opetr_char[7]={'+','-','*','/','%','(',')'};
//operational character priority (a,b),operational character b after a.
// b: + - * / % ( )
// a:
// + > > < < < < >
// - > > < < < < >
// * > > > > > < >
// / > > > > > < >
// % > > > > > < >
// ( < < < < < < =
// ) > > > > > N N
char opetr_priority[7][7]={
{'>','>','<','<','<','<','>'},
{'>','>','<','<','<','<','>'},
{'>','>','>','>','>','<','>'},
{'>','>','>','>','>','<','>'},
{'>','>','>','>','>','<','>'},
{'<','<','<','<','<','<','='},
{'>','>','>','>','>','N','N'}
};
int isOpetrChar(char ch){
int i;
for(i=0;i<7;i++){
if(ch == opetr_char[i]) return i;
}
return -1;
}
char getOpetrPrior(char a,char b){
int i = isOpetrChar(a);
int j = isOpetrChar(b);
return opetr_priority[i][j];
}
double my_pow(double a,int b){
int s = 0,i;
double r = 1;
if(b == 0) return 1;
if(b<0){
b*=-1;
s = 1;
}
for(i = 0; i < b; i++){
r *= a;
}
if(s) r = 1/r;
return r;
}
int getOpndNumFromStack(LinearListStack *opnd_stack){
int num = 0,i = 0;
char elem;
if(opnd_stack->length(opnd_stack)){
opnd_stack->pop(opnd_stack,&elem);
if(elem == ' '){
while(elem == ' '){
if(opnd_stack->length(opnd_stack) == 0) break;//確保不會(huì)pop空棧
opnd_stack->pop(opnd_stack,&elem);
}
}
if(elem != ' '){ //兩個(gè)判斷必須分開(kāi)來(lái)寫(xiě)
while(elem != ' ' && elem != '-'){
num += my_pow(10,i)*(elem - 0x30);
if(opnd_stack->length(opnd_stack) == 0) break; //確保不會(huì)pop空棧
opnd_stack->pop(opnd_stack,&elem);
i++;
}
if(elem == '-'){ //如果是負(fù)號(hào)
num = -num;
}else if(elem == ' '){ //將移出的空格間隔符再補(bǔ)進(jìn)去
opnd_stack->push(opnd_stack,&elem);
}
}
}
return num;
}
int operate(int number_a,char opetr_char,int number_b){
int result = 0;
switch(opetr_char){
case '+':
result = number_a + number_b;
break;
case '-':
result = number_a - number_b;
break;
case '*':
result = number_a * number_b;
break;
case '/':
result = number_a / number_b;
break;
case '%':
result = number_a % number_b;
break;
default:
result = number_b;
break;
}
return result;
}
void pushResultToStack(LinearListStack *opnd_stack, int result){
char elem[10],n_elem;
int i = 0,index = 0;
if(result < 0){
result = - result;
n_elem = '-';
opnd_stack->push(opnd_stack,&n_elem);
}else if(result == 0){
n_elem = '0';
opnd_stack->push(opnd_stack,&n_elem);
}
while(result > 0){
elem[index] = (result % 10) + 0x30;
result /= 10;
index++;
}
for(i=index;i>0;i--){
opnd_stack->push(opnd_stack,&elem[i-1]);
}
}
LinearListStack *evaluateExpression(char *str){
char elem,opetr_prior,opetr_char;
int cal_result = 0,number_a,number_b;
int num_before_flag = 0;
LinearListStack *optr_stack = InitLinearListStack(); //運(yùn)算符棧
LinearListStack *opnd_stack = InitLinearListStack(); //操作數(shù)棧
while(*str != '\0'){
if(isOpetrChar(*str) != -1){
if(optr_stack->length(optr_stack)){
optr_stack->getTop(optr_stack,&elem);
opetr_prior = getOpetrPrior(elem,*str);
switch(opetr_prior){
case '<': //棧頂運(yùn)算符優(yōu)先級(jí)低
if(num_before_flag == 0){ //前一個(gè)入棧的是符號(hào)
if(*str == '-'){ //此時(shí)'-'號(hào)表示為負(fù)號(hào)
opnd_stack->push(opnd_stack,str);//'-'號(hào)加入操作數(shù)棧
num_before_flag = 1; //加入的是數(shù)字
}else if(elem == '(' || *str == '('){ //多個(gè)括號(hào)與操作符相鄰的情況
optr_stack->push(optr_stack,str);
elem = ' '; //數(shù)字字符加入空格間隔符
opnd_stack->push(opnd_stack,&elem);
num_before_flag = 0;//加入運(yùn)算符
}else{
printf("Expression format error!");
break;
}
}else{ //前面有數(shù)字入棧
optr_stack->push(optr_stack,str);
elem = ' '; //數(shù)字字符加入空格間隔符
opnd_stack->push(opnd_stack,&elem);
num_before_flag = 0;//加入運(yùn)算符
}
break;
case '=':
optr_stack->pop(optr_stack,&elem);//脫括號(hào)
num_before_flag = 1; //脫括號(hào)等效為加入的是數(shù)字
break;
case '>': //棧頂運(yùn)算符優(yōu)先級(jí)高
if(num_before_flag == 0){ //前一個(gè)入棧的是符號(hào)
if(*str == '-'){ //此時(shí)'-'號(hào)表示為負(fù)號(hào)
opnd_stack->push(opnd_stack,str);//'-'號(hào)加入操作數(shù)棧
num_before_flag = 1; //加入的是數(shù)字
}else{
printf("Expression format error!");
break;
}
}else{ //前一個(gè)入棧的是數(shù)字
optr_stack->pop(optr_stack,&opetr_char);//取運(yùn)算符
number_b = getOpndNumFromStack(opnd_stack);
number_a = getOpndNumFromStack(opnd_stack);
cal_result = operate(number_a,opetr_char,number_b);
printf("%d",number_a);
printf(" %c ",opetr_char);
printf("%d = ",number_b);
printf("%d\n",cal_result);
pushResultToStack(opnd_stack, cal_result);
num_before_flag = 1; //加入的是數(shù)字
str--;
}
break;
}
}else{
//第一個(gè)運(yùn)算符，此時(shí)運(yùn)算符棧是空的
if(num_before_flag == 0){ //前面沒(méi)有數(shù)字入棧
if(*str == '-'){ //此時(shí)'-'號(hào)表示為負(fù)號(hào)
opnd_stack->push(opnd_stack,str);//'-'號(hào)加入操作數(shù)棧
num_before_flag = 1; //加入的是數(shù)字
}else if(*str == '('){
optr_stack->push(optr_stack,str);
elem = ' '; //數(shù)字字符加入空格間隔符
opnd_stack->push(opnd_stack,&elem);
num_before_flag = 0;//加入運(yùn)算符
}else{
printf("Expression format error!");
break;
}
}else{ //前面有數(shù)字入棧
optr_stack->push(optr_stack,str);
elem = ' '; //數(shù)字字符加入空格間隔符
opnd_stack->push(opnd_stack,&elem);
num_before_flag = 0;//加入運(yùn)算符
}
}
}else{
if(*str >= 0x30 && *str <= 0x39){
opnd_stack->push(opnd_stack,str);
num_before_flag = 1; //加入的是數(shù)字
}
}
str++;
}
if(*str == '\0'){ //輸入完成
while(optr_stack->length(optr_stack)){
optr_stack->pop(optr_stack,&opetr_char);//取運(yùn)算符
if(isOpetrChar(opetr_char)<5){
number_b = getOpndNumFromStack(opnd_stack);
number_a = getOpndNumFromStack(opnd_stack);
cal_result = operate(number_a,opetr_char,number_b);
printf("%d",number_a);
printf(" %c ",opetr_char);
printf("%d = ",number_b);
printf("%d\n",cal_result);
pushResultToStack(opnd_stack, cal_result);
}
}
}
DestroyLinearListStack(optr_stack);
return opnd_stack;
}
int main(void)
{
int i;
char string[1000];
LinearListStack *optr_result = NULL;
printf("please enter a expression:");
gets(string);
optr_result = evaluateExpression(string);
printf("%s = ",string);
optr_result->risePrint(optr_result);
DestroyLinearListStack(optr_result);
return 0;
}
編譯：
gcc LinearListStack.c LinearListStack.h EvaluateExpression.c -o EvaluateExpression
運(yùn)行EvaluateExpression：
please enter a expression:3+3+(4*5）
3 + 3 = 6
4 * 5 = 20
6 + 20 = 26
3+3+(4*5） = 26
please enter a expression:-2+3+4*5
-2 + 3 = 1
4 * 5 = 20
1 + 20 = 21
-2+3+4*5 = 21
please enter a expression:-2+(3+4)*-5
3 + 4 = 7
7 * -5 = -35
-2 + -35 = -37
-2+(3+4)*-5 = -37
please enter a expression:3+3+((4*5))
3 + 3 = 6
4 * 5 = 20
6 + 20 = 26
3+3+((4*5)) = 26
please enter a expression:-2+(3/4)*-5
3 / 4 = 0
0 * -5 = 0
-2 + 0 = -2
-2+(3/4)*-5 = -2
please enter a expression:-2+(3%4)*-5
3 % 4 = 3
3 * -5 = -15
-2 + -15 = -17
-2+(3%4)*-5 = -17
