基本思路
首先笤昨,用戶輸入的待求表達(dá)式瞒窒,也就是中綴表達(dá)式乡洼,對于人來說就珠,這個(gè)很好理解醒颖,但是對于計(jì)算機(jī),后綴表達(dá)式求值更加容易逼侦。如果看成一棵二叉樹榛丢,其實(shí)中綴表達(dá)式就是對一個(gè)二叉樹的中序遍歷,后綴表達(dá)式(也叫逆波蘭表達(dá)式)就是后序遍歷的結(jié)果稼病。那么主要思路就來了:先把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式掖鱼,再對后綴表達(dá)式進(jìn)行求值戏挡。
步驟一,中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式
兩個(gè)數(shù)據(jù)結(jié)構(gòu):
1,后綴表達(dá)式隊(duì)列
用于存放最后的后綴表達(dá)式
2,操作符棧
對用戶輸入的操作符進(jìn)行處理
算法偽代碼:
/*
依次讀入用戶輸入的中綴表達(dá)式
如果是數(shù)字拆檬,直接入隊(duì)
如果是操作符,如果棧為空竟贯,直接入棧
如果操作符為 ( 直接入棧
如果操作符為 ) ,依次出棧猾封,直到遇到第一個(gè)(,(和)都不入棧
如果是其他操作符(+ - * /),則和棧頂元素進(jìn)行比較優(yōu)先級
如果棧頂元素優(yōu)先級大于等于(*和/ > +和-)操作符 ,則出棧晌缘,直到棧頂元素優(yōu)先級小于操作符或棧為空
*/
//偽代碼
//后綴表達(dá)式隊(duì)列
queue num;
//操作符棧
stack option;
while(scanf("%c",&x)){
if(x 是數(shù)){
num.addBack(x); //入隊(duì)
}else if(option.empty() || x == '('){
//如果棧為空,直接入棧,如果操作符為 ( 直接入棧
option.push(x)
}else if(x == ')'){
//如果操作符為 ) ,依次出棧选酗,直到遇到第一個(gè)(,(和)都不入棧
while((tmp = option.pop()) != '('){
num.addBack(tmp);
}
}else{
//只是獲取棧首元素芒填,沒有出棧
while(1){
tmp = option.head();
if(tmp 優(yōu)先級大于等于x){
tmp1 = option.pop();
num.addBack(tmp1);
}else{
break;
}
}
option.push(x);
}
}
//最后把所有操作符入隊(duì)
while(!option.empty()){
tmp = option.pop();
num.addBack(tmp);
}
步驟二殿衰,后綴表達(dá)式計(jì)算值
數(shù)據(jù)結(jié)構(gòu):
結(jié)果棧
用于存放計(jì)算的中間過程的值和最終結(jié)果
算法偽代碼:
/*
依次從后綴表達(dá)式隊(duì)列中取值
如果是值盛泡,直接入棧
如果是操作符傲诵,從隊(duì)列中取出兩個(gè)數(shù)箱硕,進(jìn)行運(yùn)算(后取出來的數(shù)作為第一個(gè)運(yùn)算符)悟衩,計(jì)算結(jié)果再次壓棧
*/
//用于存放結(jié)果的棧
stack res;
//后綴表達(dá)式隊(duì)列座泳,上一步求出來的
queue num;
while(!num.empty()){
//取隊(duì)首
tmp = num.getFront();
if(tmp 是數(shù)){
res.push(tmp);
}else{
num1 = num.pop();
num2 = num.pop();
num3 = num2 tmp num1;
res.push(num3);
}
}
步驟三钳榨,轉(zhuǎn)二叉樹
算法偽代碼:
/*
主要是在計(jì)算逆波蘭表達(dá)式的時(shí)候,構(gòu)造出一棵二叉樹营罢,
構(gòu)造思路和計(jì)算時(shí)差不多饲漾,如果是數(shù)缕溉,就直接構(gòu)造節(jié)點(diǎn),如果是操作符僚楞,就把前面兩個(gè)節(jié)點(diǎn)提出來作為左右節(jié)點(diǎn)
*/
//用于存放所有臨時(shí)節(jié)點(diǎn)和最后根節(jié)點(diǎn)的數(shù)組
treeNode all[MAX];
int n=0;
//后綴表達(dá)式隊(duì)列泉褐,上一步求出來的
queue num;
while(!num.empty()){
//取隊(duì)首
tmp = num.getFront();
if(tmp 是數(shù)){
res[n++] = tmp;
}else{
num1 = all[--n];
num2 = all[--n];
tmp.left = num1;
tmp.right = num2;
all[n++] = tmp;
}
}
運(yùn)行情況
完整代碼
/**
* 計(jì)算算術(shù)表達(dá)式的值膜赃,支持 加減乘除括號(hào) 運(yùn)算
* 思路是揉忘,先把用戶輸入的表達(dá)式(中綴表達(dá)式泣矛,中序遍歷),格式化成逆波蘭表達(dá)式(后綴表達(dá)式咪橙,后序遍歷序列)
* 再對后綴表達(dá)式進(jìn)行求值
*/
#include <stdio.h>
#include <string.h>
//通用鏈表
#include "cl_link.h"
#define MAX 1024
#define IS_OPTION '0'
#define IS_NUM '1'
char* optionAll = "+-*/()";
typedef struct bTree{
char type;
double num;
char option;
struct bTree* left;
struct bTree* right;
}bTree;
//運(yùn)算符節(jié)點(diǎn)
typedef struct optionNode{
//用于標(biāo)志運(yùn)算符
char type;
cl_link_node node;
char option;
}optionNode;
//操作數(shù)節(jié)點(diǎn)
typedef struct numNode{
// 用于標(biāo)志操作數(shù)
char type;
cl_link_node node;
double num;
}numNode;
//運(yùn)算符棧
cl_link* optionStack = NULL;
//數(shù)字隊(duì)列
cl_link* numQueue = NULL;
/**
* 比較是否是運(yùn)算符
* @param optionAll 運(yùn)算符表
* @param aim 比較對象
* @return 1 是 0 不是
*/
int isOption(const char* optionAll,const char aim)
{
for (size_t i = 0; i < strlen(optionAll); i++) {
if(aim == *(optionAll+i)){
return 1;
}
}
return 0;
}
/**
* 比較優(yōu)先級
* @return 1 src >= des
* 0 src < des
*/
int isMaxLevel(const char src, const char des)
{
if(src == '*' || src == '/')
return 1;
if((src == '+' || src == '-') && (des == '+' || des == '-'))
return 1;
return 0;
}
void* show(void* arg)
{
numNode* node = cl_link_get_data(arg, numNode, node);
if(node->type == IS_NUM){
printf("%0.2f,", node->num);
}else{
optionNode* node1 = cl_link_get_data(arg, optionNode, node);
printf("%c,", node1->option);
}
return NULL;
}
//計(jì)算
double cal(double num1, double num2, char option)
{
switch (option) {
case '+':
return num1+num2;
case '-':
return num1-num2;
case '*':
return num1*num2;
case '/':
return num1/num2;
}
return 0;
}
void pre(bTree* root){
if(root != NULL)
{
if(root->type == IS_NUM){
printf("%0.2f,", root->num);
}else{
printf("%c,", root->option);
}
pre(root->left);
pre(root->right);
}
}
void mid(bTree* root){
if(root != NULL)
{
mid(root->left);
if(root->type == IS_NUM){
printf("%0.2f,", root->num);
}else{
printf("%c,", root->option);
}
mid(root->right);
}
}
void back(bTree* root){
if(root != NULL)
{
back(root->left);
back(root->right);
if(root->type == IS_NUM){
printf("%0.2f,", root->num);
}else{
printf("%c,", root->option);
}
}
}
int main()
{
//初始化運(yùn)算符棧
optionStack = cl_link_create();
//初始化逆波蘭空隊(duì)列魂奥,即后序遍歷結(jié)果
numQueue = cl_link_create();
//把輸入格式化成后綴表達(dá)式 開始
char expr[MAX];
scanf("%s", expr);
for (size_t i = 0; i < strlen(expr); i++) {
//假設(shè)輸入完全合法,不是運(yùn)算符就是運(yùn)算數(shù)
if(!isOption(optionAll, *(expr+i))){
//運(yùn)算數(shù)具壮,直接入隊(duì)哈蝇,numQueue
numNode* node = malloc(sizeof(numNode));
node->num = atoi(expr+i);
node->type = IS_NUM;
int tmp = node->num;
while(tmp/10 > 0){
i++;
tmp /= 10;
}
//入隊(duì)
cl_link_add_back(numQueue, cl_link_get_node(node, numNode, node));
}else{
/**
* 如果棧為空炮赦,直接入棧
* 如果是( 直接入棧
* 如果是) 則依次出棧到隊(duì)列中,直到遇到第一個(gè)(
* 如果X是其他運(yùn)算符性芬,則依次與棧頂元素比較優(yōu)先級植锉,
* 如果棧頂元素的優(yōu)先級大于等于X峭拘,
* 則出棧鸡挠,直到棧頂元素的優(yōu)先級小于X或者棧為空。
* 否則 入棧
*/
optionNode* node = malloc(sizeof(optionNode));
node->type = IS_OPTION;
node->option = *(expr+i);
if(optionStack->sum == 0 || *(expr+i) == '('){
//如果棧為空鞋囊,或者是(瞎惫,直接入棧
cl_link_push(optionStack, cl_link_get_node(node, optionNode, node));
}else if(*(expr+i) == ')'){
//如果是) 則依次出棧到隊(duì)列中瓜喇,直到遇到第一個(gè)(
while(1){
optionNode* tmp = cl_link_get_data(cl_link_pop(optionStack), optionNode, node);
if(tmp->option == '('){
break;
}else{
cl_link_add_back(numQueue, cl_link_get_node(tmp, optionNode, node));
}
}
}else{
printf("%C,", *(expr+i));
//如果X是其他運(yùn)算符乘寒,則依次與棧頂元素比較優(yōu)先級,如果棧頂元素的優(yōu)先級大于等于X烂翰,則出棧,直到棧頂元素的優(yōu)先級小于X或者棧為空踊兜。
while(1){
//得到棧頂元素
optionNode* tmp = cl_link_get_data(cl_link_get_head(optionStack), optionNode, node);
if(isMaxLevel(tmp->option, *(expr+i))){
//如果優(yōu)先級大于運(yùn)算符捏境,就出棧到逆波蘭隊(duì)列
optionNode* tmp = cl_link_get_data(cl_link_pop(optionStack), optionNode, node);
cl_link_add_back(numQueue, cl_link_get_node(tmp, optionNode, node));
}else{
break;
}
}
optionNode* node = malloc(sizeof(optionNode));
node->type = IS_OPTION;
node->option = *(expr+i);
cl_link_push(optionStack, cl_link_get_node(node, optionNode, node));
}
}
}
/**
* 若運(yùn)算符還有垫言,則直接出棧
*/
while(optionStack->sum != 0){
optionNode* tmp = cl_link_get_data(cl_link_pop(optionStack), optionNode, node);
cl_link_add_back(numQueue, cl_link_get_node(tmp, optionNode, node));
}
//把輸入格式化成后綴表達(dá)式 結(jié)束
printf("\n逆波蘭表達(dá)式(后序遍歷):");
//打印逆波蘭式倾剿,就是后序遍歷結(jié)果
cl_link_each(numQueue, NULL, show);
bTree* allTreeNode[MAX];
int n = 0;
//計(jì)算逆波蘭表達(dá)式結(jié)果柱告,用于存放臨時(shí)結(jié)果和最終結(jié)果
cl_link* res = cl_link_create();
while(numQueue->sum != 0){
numNode* tmp = cl_link_get_data(cl_link_pop(numQueue), numNode, node);
if(tmp->type == IS_NUM){
//如果是數(shù)际度,直接入棧
cl_link_push(res, cl_link_get_node(tmp, numNode, node));
bTree* newNode = malloc(sizeof(bTree));
newNode->left = NULL;
newNode->right = NULL;
newNode->type = IS_NUM;
newNode->num = tmp->num;
allTreeNode[n++] = newNode;
}else{
//如果是操作符,則pop出棧頂兩個(gè)元素坡锡,進(jìn)行運(yùn)算鹉勒,再入棧
optionNode* tmpOption = (optionNode*)tmp;
numNode* num1 = cl_link_get_data(cl_link_pop(res), numNode, node);
numNode* num2 = cl_link_get_data(cl_link_pop(res), numNode, node);
numNode* node = malloc(sizeof(numNode));
node->num = cal(num2->num, num1->num, tmpOption->option);
node->type = IS_NUM;
cl_link_push(res, cl_link_get_node(node, numNode, node));
bTree* newNode = malloc(sizeof(bTree));
newNode->left = NULL;
newNode->right = NULL;
newNode->type = IS_OPTION;
newNode->option = tmpOption->option;
newNode->right = allTreeNode[--n];
newNode->left = allTreeNode[--n];
allTreeNode[n++] = newNode;
}
}
numNode* resData = cl_link_get_data(cl_link_get_head(res), numNode, node);
printf("\n運(yùn)算結(jié)果是%0.2f\n", resData->num);
printf("前序遍歷\n");
pre(allTreeNode[0]);
printf("\n中序遍歷\n");
mid(allTreeNode[0]);
printf("\n后序遍歷\n");
back(allTreeNode[0]);
printf("\n\n");
return 0;
}
涉及的隊(duì)列和棧數(shù)據(jù)結(jié)構(gòu)代碼
cl_link.h
#ifndef _CL_LINK_H
#define _CL_LINK_H
#include <pthread.h>
#include <malloc.h>
#include <unistd.h>
#include <stdlib.h>
#define ADD_SUCCESS (0)
#define ADD_FAIL (-1)
#define DELETE_SUCCESS (0)
#define SELETE_FAIL (-1)
#define CANFIND (1)
#define NOTFIND (0)
typedef struct cl_link_node cl_link_node;
typedef struct cl_link cl_link;
/**
* 鏈表節(jié)點(diǎn)禽额,其他結(jié)構(gòu)體需要使用鏈表數(shù)據(jù)結(jié)構(gòu)脯倒,只需包含此節(jié)點(diǎn)
* @return
*/
typedef struct cl_link_node{
cl_link_node* next;
cl_link_node* prev;
}cl_link_node;
/**
* 通用鏈表對象
* @return
*/
typedef struct cl_link{
pthread_mutex_t cl_link_mutex; //鏈表鎖
cl_link_node cl_link_head; //鏈表頭
cl_link_node cl_link_tail; //鏈表尾
int sum; //節(jié)點(diǎn)數(shù)
}cl_link;
#define cl_link_get_node(aim, type, node) \
(cl_link_node *) ((u_char *) aim + offsetof(type, node))
#define cl_link_get_data(aim, type, node) \
(type *) ((u_char *) aim - offsetof(type, node))
/**
* 創(chuàng)建一個(gè)鏈表對象
* @return 鏈表對象地址
*/
cl_link* cl_link_create();
/**
* 鏈表的壓棧操作
* @param link 鏈表對象
* @param node 新節(jié)點(diǎn)
* @return 壓棧狀態(tài)
*/
int cl_link_push(cl_link* link, void* node);
/**
* 鏈表的出棧操作
* @param link 鏈表對象
*/
void* cl_link_pop(cl_link* link);
//獲取棧頂元素
void* cl_link_get_head(cl_link* link);
/**
* 對每個(gè)節(jié)點(diǎn)進(jìn)行操作
* @param link 鏈表對象
* @param res 返回值
* @param handler 處理函數(shù)
*/
void cl_link_each(cl_link* link, void* res[], void* (*handler)(void* node));
/**
* 隊(duì)尾添加元素
* @param link 隊(duì)列對象
* @param node 新節(jié)點(diǎn)
* @return 添加狀態(tài)
*/
int cl_link_add_back(cl_link* link, void* node);
/**
* 隊(duì)頭獲取元素
* @param link 隊(duì)列對象
* @return 取得的元素
*/
void* cl_link_get_front(cl_link* link);
/**
* 根據(jù)key查找節(jié)點(diǎn)
* @param link 鏈表對象
* @param key 關(guān)鍵字
* @param condition 條件
*/
void* cl_link_find(cl_link* link, void* key, int (*condition)(void* node, void* key));
#endif
cl_link.c
#include "cl_link.h"
/**
* 創(chuàng)建一個(gè)鏈表對象
* @return 鏈表對象地址
*/
cl_link* cl_link_create()
{
cl_link* link = malloc(sizeof(cl_link));
if(link == NULL){
write(STDERR_FILENO, "malloc error", sizeof("malloc error"));
return NULL;
}
pthread_mutex_init(&(link->cl_link_mutex), NULL);
pthread_mutex_lock(&(link->cl_link_mutex));
link->cl_link_head.next = &(link->cl_link_tail);
link->cl_link_head.prev = &(link->cl_link_tail);
link->cl_link_tail.next = &(link->cl_link_head);
link->cl_link_tail.prev = &(link->cl_link_head);
link->sum = 0;
pthread_mutex_unlock(&(link->cl_link_mutex));
return link;
}
/**
* 鏈表的壓棧操作
* @param link 鏈表對象
* @param node 新節(jié)點(diǎn)
* @return 壓棧狀態(tài)
*/
int cl_link_push(cl_link* link, void* node)
{
cl_link_node* new_node = (cl_link_node*)node;
pthread_mutex_lock(&(link->cl_link_mutex));
if(link)
{
new_node->next = link->cl_link_head.next;
link->cl_link_head.next->prev = new_node;
link->cl_link_head.next = new_node;
new_node->prev = &(link->cl_link_head);
link->sum++;
pthread_mutex_unlock(&(link->cl_link_mutex));
return ADD_SUCCESS;
}else{
pthread_mutex_unlock(&(link->cl_link_mutex));
return ADD_FAIL;
}
}
/**
* 鏈表的出棧操作
* @param link 鏈表對象
*/
void* cl_link_pop(cl_link* link)
{
pthread_mutex_lock(&(link->cl_link_mutex));
if(link->sum){
cl_link_node* aim = link->cl_link_head.next;
link->cl_link_head.next = aim->next;
aim->next->prev = &(link->cl_link_head);
link->sum--;
pthread_mutex_unlock(&(link->cl_link_mutex));
return aim;
}else{
pthread_mutex_unlock(&(link->cl_link_mutex));
return NULL;
}
}
void* cl_link_get_head(cl_link* link)
{
return link->cl_link_head.next;
}
/**
* 對每個(gè)節(jié)點(diǎn)進(jìn)行操作
* @param link 鏈表對象
* @param res 返回值
* @param handler 處理函數(shù)
*/
void cl_link_each(cl_link* link, void* res[], void* (*handler)(void* node))
{
pthread_mutex_lock(&(link->cl_link_mutex));
int n = link->sum;
void* r;
cl_link_node* p = link->cl_link_head.next;
cl_link_node* todo = p;
while(n)
{
todo = p;
p = p->next;
r = handler(todo);
if(res != NULL)
{
res[link->sum-n] = r;
}
n--;
}
pthread_mutex_unlock(&(link->cl_link_mutex));
}
/**
* 隊(duì)尾添加元素
* @param link 隊(duì)列對象
* @param node 新節(jié)點(diǎn)
* @return 添加狀態(tài)
*/
int cl_link_add_back(cl_link* link, void* node)
{
cl_link_node* new_node = (cl_link_node*)node;
pthread_mutex_lock(&(link->cl_link_mutex));
if(link)
{
new_node->next = &(link->cl_link_tail);
new_node->prev = link->cl_link_tail.prev;
link->cl_link_tail.prev->next = new_node;
link->cl_link_tail.prev = new_node;
link->sum++;
pthread_mutex_unlock(&(link->cl_link_mutex));
return ADD_SUCCESS;
}else{
pthread_mutex_unlock(&(link->cl_link_mutex));
return ADD_FAIL;
}
}
/**
* 隊(duì)頭獲取元素
* @param link 隊(duì)列對象
* @return 取得的元素
*/
void* cl_link_get_front(cl_link* link)
{
return cl_link_pop(link);
}
/**
* 根據(jù)key查找節(jié)點(diǎn)
* @param link 鏈表對象
* @param key 關(guān)鍵字
* @param condition 條件
*/
void* cl_link_find(cl_link* link, void* key, int (*condition)(void* node, void* key))
{
pthread_mutex_lock(&(link->cl_link_mutex));
int n = link->sum;
cl_link_node* p = link->cl_link_head.next;
while(n)
{
if(condition(p, key) == CANFIND)
{
pthread_mutex_unlock(&(link->cl_link_mutex));
return p;
}
p = p->next;
n--;
}
pthread_mutex_unlock(&(link->cl_link_mutex));
return NULL;
}