溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
中綴表達式：
把運算符放在參與運算的兩個操作數中間的表達式稱作中綴表達式例：“3+4*5-6/2”，因為中綴表達式計算時必須按照優先級從左向右計算，所以計算機在進行中綴表達式求值時比較麻煩，而后綴表達式求值比較方便。
后綴表達式：
把運算符放在參與運算的兩個操作數后面的表達式稱作后綴表達式。
例：中綴表達式：3+4*5-6/2
轉換成后綴表達式： 3 4 5 * + 6 2 / -
中綴表達式：9-8*（4-3）
轉換成后綴表達式： 9 8 4 3 - * -
轉換規則：
按照優先級，把每個運算符都移到它的兩個操作數的后面，再刪除所有的括號
后綴表達式的求值：
從左向右一次掃描后綴表達式，遇到運算符將將它前面的兩個運算數取出并計算，并將結果帶入后綴表達式，直到掃描到最后一個后綴表達式。
表達式求值：
表達式求值是棧應用的一個基本例子，輸入一個中綴表達式，求取相應的結果。因為計算機不會算中綴表達式，所以我們先要將中綴表達式轉換成相應的后綴表達式再進行計算。要轉成相應的后綴表達式，我們應該創建兩個棧，一個用來存放操作數，一個用來存放運算符。
中綴表達式求值的算法：
從左向右掃描中綴表達式，若遇到操作數，則直接壓入運算數棧，若遇到符號，則與運算符棧的棧頂元素比較，若讀取符號的優先級高，則讀取的符號進棧；否則讓運算符棧的棧頂符號退棧并且將運算數棧最上面的兩個元素退棧，然后將運算的結果壓入運算數棧，一直這樣循環直到讀取的符號的優先級高于運算符棧頂元素。
因為每讀取一個符號就要與運算符棧的棧頂元素進行優先級比較，我們不能每次都寫一大堆if else語句，所以我們可以將運算符的優先級的結果放到一個二維數組中，然后利用查表法，判斷優先級。
因為當我們讀取第一個符號時，運算符棧還是個空棧，為了方便比較，我們在棧底壓入一個#，并規定#的優先級最低，并將“#”作為表達式輸入結束的標志。
為了方便索引：我們再創建一個一維數組，
char arr[7] = { '+' , '-', '*', '/', '(', ')', '#' };通過它來找到棧頂符號和讀取符號在優先級數組中的位置。
實現：輸入一個合法的中綴表達式，只包含“+ - * /”四種運算符，并以“#”作為結束標志。
//函數聲明：
#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_MEMORY 20 //初始時開辟棧的內存大小
#define STACK_GROW_MEMORY 10 //當棧滿時，追加內存的大小
const char arr[7]; //聲明一個存放運算符的一維數組，作為索引
void init_priority_list(char list[][7]); //初始化符號表
typedef struct stack_num //聲明一個存放運算數的結構體類型
{
int *esp; //棧頂指針
int *ebp; //棧底指針
int size; //記錄當前棧空間最多能存幾個元素
}stack_num;
void creatstack_num(stack_num *S); //創建存放運算數的棧
void push_num(stack_num *S, int x); //將參數x中的數壓入運算數棧中
int pop_num(stack_num *S, int *x); //彈出棧頂元素，并通過形參x帶回
typedef struct stackpop_opreation //聲明一個存放運算符的結構體類型
{
char *esp; //棧頂指針
char *ebp; //棧底指針
int size; //記錄當前棧空間最多能存幾個元素
}stack_operation;
void creatstack_operation(stack_operation *S); //創建一個存放運算符的棧
void push_operation(stack_operation *S, char symbol); //將符號壓入運算符棧中
int pop_opreation(stack_operation *S, char *top); //將運算符棧中的棧頂元素彈出
//函數實現：
char judge_priority(stack_operation* S, char c); //判斷讀取的運算符與棧頂符號的優先級,并返回
int operation(int a, char symbol, int b); //對運算數進行相的運算，并將結果返回
int judge_num(char c); //判斷讀取的是符號還是數字，如果是數字返回1
#include"expression.h"
const char arr[7] = { '+', '-', '*', '/', '(', ')', '#' }; //通過arr[7]來查找list[][]中的優先級
void init_priority_list(char list[][7]) //初始化優先級列表
{
int arr2[7] = { 1, 1, 2, 2, 3, 0, -1 }; //列作為棧頂元素，行代表讀取的運算符
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 7; j++)
{
if ((i == 4 && j == 5) || (i == 6 && j == 6) //令'('與‘）’，‘#’與‘#’優先級相同
list[i][j] = '=';
else
{
if (arr2[i] >= arr2[j])
list[i][j] = '>'; //棧頂優先級高
else if (arr2[i] <= arr2[j])
list[i][j] = '<'; //讀取的運算符優先級高
}
}
}
}
void creatstack_num(stack_num *S) //創建運算數棧
{
S->ebp = (int *)malloc(sizeof(int)* STACK_INIT_MEMORY);
if (S->ebp == NULL) //判斷動態內存是否開辟成功
exit(1);
S->size = STACK_INIT_MEMORY;
S->esp = S->ebp; //讓棧頂指針指向棧底
}
void push_num(stack_num *S, int x)
{
if (S->esp - S->ebp >= S->size) //判斷當前棧是否已滿
{ //棧滿追加空間
S->ebp = (int *)realloc(S->ebp, sizeof(int)*(S->size + STACK_GROW_MEMORY));
if (S->ebp == NULL)
exit(1);
S->esp = S->ebp + S->size; //讓棧頂指針向后偏移指向要入棧的位置
S->size += STACK_GROW_MEMORY; //更新棧的size
}
*S->esp++ = x;
}
int pop_num(stack_num *S, int *x)
{
if (S->esp == S->ebp)
return 0; //如果是空棧，則返回0
else
{
*x = *--S->esp;
return 1; //如果彈出成功，返回1，并將彈出的元素保存在x中帶回
}
}
void creatstack_operation(stack_operation *S) //創建運算符棧
{
S->ebp = (char *)malloc(sizeof(char)*STACK_INIT_MEMORY);
if (S->ebp == NULL)
exit(1); //判斷動態內存是否開辟成功
S->size = STACK_INIT_MEMORY;
S->esp = S->ebp;
}
void push_operation(stack_operation *S, char symbol)
{
if (S->esp - S->ebp >= S->size) //如果棧滿則追加空間
{
S->ebp = (char *)realloc(S->ebp, sizeof(char)*(S->size += STACK_GROW_MEMORY));
if (S->ebp == NULL)
exit(1);
S->ebp = S->ebp + S->size - STACK_GROW_MEMORY;
}
*S->esp++ = symbol;
}
int pop_opreation(stack_operation *S, char *top)
{
if (S->esp == S->ebp)
return 0; //如果棧是空棧，則返回0
else
*top = *--S->esp; //否則將彈出的勻速保存在top中帶回
return 1;
}
char judge_priority(stack_operation* S, char c) //判斷棧頂運算符與讀取的運算符的優先級
{
char list[7][7];
init_priority_list(list); //初始化優先級表
int line = 0;
int row = 0;
for (line = 0; line < 7; line++)
{
if (arr[line] == *(S->esp - 1)) //將棧頂符號在arr[]中的位置作為行下標
break;
}
for (row = 0; row < 7; row++)
{
if (arr[row] == c) //將讀取的運算符在arr[]中的位置作為列下標
break;
}
return list[line][row]; //通過優先級表，返回優先級關系
}
int operation(int a, char symbol, int b)
{
int ret = 0;
switch (symbol)
{
case '+':
ret = a + b;
break;
case '-':
ret = a - b;
break;
case '*':
ret = a*b;
break;
case '/':
ret = a / b;
break;
default:
break;
}
return ret;
}
int judge_num(char c) //判斷讀取的是不是數字
{
int i = 0;
for (i = 0; i < 7; i++)
{
if (arr[i] == c)
break;
}
if (i == 7)
return 1; //如果是數字則返回1
else
return 0; //如果不是數字則返回0
}
#include"expression.h"
int main()
{
stack_num num_stack;
creatstack_num(&num_stack); //建立一個運算數棧
stack_operation operator_stack;
creatstack_operation(&operator_stack); //建立一個運算符棧
int c;
char symbol;
int a = 0;
int b = 0;
int ret = 0;
push_operation(&operator_stack, '#'); //將‘#’入棧，作為運算符棧的棧底
c=getchar();
while (c!='#'||*(operator_stack.esp-1)!='#'） //接受表達式并且判斷表達式是否輸入完畢
{
if (judge_num(c)) //如果是數字則進入運算數棧
{
int num = 0;
while (judge_num(c)) //把連續的char類型的數字全部讀取并轉化成相應的整數
{
num = num * 10 + (c-'0'); //因為這是的運算數是char類型，所以先要轉換成int
c = getchar();
}
push_num(&num_stack,num); //將運算數入棧
}
else
{
switch (judge_priority(&operator_stack,c)) //判斷讀取的運算符與棧頂符號的優先級關系
{
case '<': //如果讀取的符號優先級高，則直接進入運算符棧
push_operation(&operator_stack, c);
c=getchar();
break;
case '>': //如果讀取的符號優先級低，則棧頂符號退棧，將運算結果入棧
pop_opreation(&operator_stack, &symbol); //則棧頂符號退棧
pop_num(&num_stack, &b);
pop_num(&num_stack, &a) // 將運算數棧棧頂的兩個元素彈出
ret=operation(a, symbol, b); //將這兩個元素進行運算
push_num(&num_stack, ret); //將運算結果入棧
break;
case '=': //當讀取到“）”時則一直退棧直到遇到“（”
pop_opreation(&operator_stack, &symbol);
c=getchar();
break;
default:
break;
}
}
}
printf("%d\n", *(num_stack.esp-1)); //將運算數棧最后剩下的數輸出
system("pause");
free(num_stack.ebp);
free(operator_stack.ebp);
return 0;
}免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
