首页 > 代码库 > 算法学习 - 后缀表达式 (C++ 栈实现)
算法学习 - 后缀表达式 (C++ 栈实现)
后缀表达式就是把一个式子进行树的后序遍历。然后根据这个顺序来求值。
栈来实现的时候很简单。
例如中缀表达式:6 * [ 5 + ( 2 + 3 ) * 8 + 3 ]
则 后缀表达式为:6 5 2 3 + 8 * + 3 + *
下面上代码:
// // main.cpp // postfixExpression // // Created by Alps on 14-7-28. // Copyright (c) 2014年 chen. All rights reserved. // #include <iostream> #define ElementType double using namespace std; struct Node; typedef Node * PtrToNode; typedef PtrToNode Stack; struct Node{ ElementType X; PtrToNode Next; }; Stack createStack(){ Stack S; S = (Stack)malloc(sizeof(Stack)); S->Next = NULL; return S; } int isEmpty(Stack S){ return S->Next == NULL; } void Push(Stack S, ElementType element){ Stack tmp; tmp = (Stack)malloc(sizeof(Stack)); tmp->X = element; tmp->Next = S->Next; S->Next = tmp; } ElementType Top(Stack S){ if (!isEmpty(S)) { return S->Next->X; }else{ printf("Stack is empty, can't return top element!\n"); return 0; } return 0; } void Pop(Stack S){ if (!isEmpty(S)) { Stack tmp = S->Next; S->Next = tmp->Next; free(tmp); }else{ printf("Stack is empty, can't pop!\n"); } } int makeEmpty(Stack S){ if (S == NULL) { printf("please create stack first!\n"); return 0; } while (!isEmpty(S)) { Pop(S); } return 0; } void stackAdd(Stack S){ double tmp1, tmp2; tmp1 = Top(S); Pop(S); tmp2 = Top(S); Pop(S); tmp1 += tmp2; Push(S, tmp1); } void stackSubstraction(Stack S){ double tmp1,tmp2; tmp1 = Top(S); Pop(S); tmp2 = Top(S); Pop(S); tmp1 -= tmp2; Push(S, tmp1); } void stackMultiplication(Stack S){ double tmp1,tmp2; tmp1 = Top(S); Pop(S); tmp2 = Top(S); Pop(S); tmp1 *= tmp2; Push(S, tmp1); } void stackDivision(Stack S){ double tmp1,tmp2; tmp1 = Top(S); Pop(S); tmp2 = Top(S); Pop(S); tmp1 = tmp1/tmp2; Push(S, tmp1); } void postfixExpression(Stack S, char *A, int length){ int i = 0; double tmp1; for (i = 0; i < length; i++) { switch (A[i]) { case '+': stackAdd(S); break; case '-': stackSubstraction(S); break; case '*': stackMultiplication(S); break; case '/': stackDivision(S); break; default: tmp1 = (int)A[i]-48; Push(S, tmp1); break; } } } int main(int argc, const char * argv[]) { char A[]={'6','5','2','3','+','8','*','+','3','+','*'}; int lengthA = sizeof(A)/sizeof(char); Stack S = createStack(); double result; postfixExpression(S, A, lengthA); result = Top(S); printf("%.2f\n",result); return 0; }
这个字符串我自己定义了,可以手动输入,但其实我没有对错误输入进行判断,假如需要的话,自己判断就可以了,因为我把错误情况已经列出来了。
但是没有对错误的情况进行输出。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。