数据结构，用逆波兰表达式求四则混合运算的值，使用C/C++-学网-中国IT综合门户网站-提供健康,养生,留学,移民,创业,汽车等信息
> 信息中心 >
数据结构，用逆波兰表达式求四则混合运算的值，使用C/C++
来源：互联网 发表时间： 8:03:10 责任编辑：王亮字体：
为了帮助网友解决“数据结构，用逆波兰表达式求四则混合运算的值，使用C/C++”相关的问题，学网通过互联网对“数据结构，用逆波兰表达式求四则混合运算的值，使用C/C++”相关的解决方案进行了整理,用户详细问题包括:
利用逆波兰表达式求一个四则混合元算的值。
具体要求：
1、 定义二叉树的型BTREE和位置的型position。
2、 实现二叉树的基本操作。
3、 实现将一个四则混合运算转换成二叉树的函数：BTREEconvert(char *express)，其中参数express为四则混合运算表达式...
2。具体要求、 实现计算四则混合运算的值的函数，其中，然后利用栈结构计算表达式的值，其中参数express为四则混合运算表达式、 定义二叉树的型BTREE和位置的型position。4：1、 实现将一个四则混合运算转换成二叉树的函数，返回值为生成的树。提示、 实现二叉树的基本操作。3，求2+3*（5+8）/4-5的值，参数bt为四则运算所对应的树：BTREEconvert(char *express)：doublecomputer(BTREE bt)。在主函数中进行测试，返回值为计算结果：先求树的的波兰表达式利用逆波兰表达式求一个四则混合元算的值
，具体解决方案如下：解决方案1：
&&&}&&&&9'&&&&&&&&&&&&&&nbsp.top--.data[s;&i=1;&&&&时只要栈顶元素不等于’（‘就出栈然后跳过括号只剩下加减乘除的运算符了那么+-的级别最低所以直接把前面的字符出栈;&&&&nbsp,当字符为'&&&&&ch=str[0];&nbsp!='&&&&s;exp[t]=s;&='&&&&&&&&&&&s;&&{&&&&&&nbsp！这个二叉树递归来递归去搞得人都不好了;&&&&exp[t]=&#39.top]=='&&t++;&&&nbsp.top]=&&{&&case'&&&&nbsp!=-1)&'&&&&&&i--;&&nbsp.top];&&&&&&&&&&&&&)&&&&&)'&&&&&&||s;#&#39.top--;&nbsp,char*exp){&&&&&&&&&&&&&&&&&&&&&&&&&&s.data[s;MaxLen&int&&&&&&&&&&&&&&)&&&&{&&nbsp.top];&&&&&-'&case'&&&ch=str[i];&&&;&&&&&&&&&&&&&&&&&while(s;case'('&s;&&&&&&&exp[t]=s;&&&&&&&&&nbsp:&&data[MaxLen];)&&&&;&&&&&nbsp.data[s;&&&&nbsp.top--;1000void&&&&&&GetExp(char&&&&+'&&&nbsp.top=-1;&&&s;&&&&&;&&&&&&!='&&&&nbsp.top++;&nbsp！将中缀表达式转换为后缀表达式的搞法;&&&&&&&&&&{&&ch=str[i];&&&&&&&&&&&&&&&&&&nbsp:&nbsp.data[s！将中缀表达式转换成后缀表达式;&&&&&&&&&&&nbsp.top]=&&&&&&&&&&&&&&&&&&&&&&&&&s;s;&nbsp.&&&&&&&&&&&&t++;&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&nbsp:&&&&&&&&&&&&nbsp你可以直接利栈来写吧.data[s;&case'&&switch(ch)&&&&}&)'&&&&&nbsp.top]=&{&&&&&&&&&&&&&&&&&&&&&while(s;&&&&&&&&&&&&&&int&&s;&&&&&&&while(s;;&&nbsp:&&&&&&nbsp：与栈顶元素比较优先级高的进栈否者出栈到后缀表达式中表达式中有+;&&&&&&}&&&&&&&&nbsp.top])=='s;&&&&nbsp.data[s;&&&&&('&&&case&)&&&&&&&&&&&&&&i++;&&nbsp:&&&&&&t++;}&&&&&&&nbsp.data[s;case&&&i++;&&&&&&&&&&&&&&nbsp.top];&&&& 进栈;&&&&&;&&&&&}&&&&&&&&&*或者/进栈数字字符直接输出#define&&&&&('&s;&&nbsp!='&&&&&&&&&s:&&&&&&'&&&&&&*'&&&&&nbsp.top--;&&char&&&&&&&&&&&&&&nbsp:&)&&&{&&case'&&&&&&&&&&s;&}s;&&&&&&&&&&&&&&&&&&struct&nbsp.top];&&&&&&='while(&nbsp.top++;&&&;&&&'&&&&&&&{&&&&nbsp，-*;&&&nbsp.top--;&&&&&&&&&&&&&stack&&&nbsp.data[s;char&&&&//跳过括号&&&&/'}&&&&exp[t]=&&nbsp.top++;&&&&&**'while(ch&&&&&&&&&&&s;&&&&&&&&&&&&&&&&&&nbsp.data[s;&&nbsp,/（ )现在我们来看他们的优先级毋庸置疑括号的优先级最高所以‘（'&&&&&&&&&&t++;&&nbsp，t=0;&&&;&&&&&&nbsp.&&&&&&&&&&ch&&&&&&nbsp.data[s.data[s;\0'&&&&&{&&&&&&&&&&&&&&&&&&&&0'exp[t]=s;&&&&&&exp[t]=s，然后再把现在的加或者减运算符入栈*/时因为这两个的优先级高所以栈顶元素等于* /时出栈直到栈顶元素优先级比*/小 时 &&&&&&&&&&&&&&&nbsp.top];&&&&&&&&while(s;&&&&&&&&&&&&nbsp.top];&&&&&&&&&&t++;&&&&t++！=-1&&nbsp！然后还是利用栈来计算;&&&&&&&&&&&&&&nbsp:&&&&/'&&&nbsp
1个回答1个回答1个回答1个回答1个回答1个回答1个回答1个回答1个回答1个回答1个回答1个回答
相关文章：
最新添加资讯
24小时热门资讯
Copyright © 2004- All Rights Reserved. 学网 版权所有
京ICP备号-1 京公网安备02号栈的当用之求逆波兰表达式的值 - Ruby/Rails当前位置:& &&&栈的当用之求逆波兰表达式的值栈的当用之求逆波兰表达式的值&&网友分享于：&&浏览：0次栈的应用之求逆波兰表达式的值
1 #include&stdio.h&
2 #include&stdlib.h&
3 #include&ctype.h&
5 #define OK
6 #define ERROR
7 #define STACK_INIT_SIZE 20
8 #define STACK_INCREMENT 10
9 #define DIGITBUFFER
11 typedef int
12 typedef double E
13 typedef struct StackNode{
Elemtype* base;
int stackS
17 }StackN
18 typedef struct StackNode* S
20 Status InitStack(Stack s){
s-&base = (Elemtype*)malloc(sizeof(Elemtype) * STACK_INIT_SIZE);
if(!s-&base)
return ERROR;
s-&top = s-&base;
s-&stackSize = STACK_INIT_SIZE;
return OK;
28 Status Pop(Stack s,Elemtype* result){
if(s-&base == s-&top)
return ERROR;
*result = *(--s-&top);
return ERROR;
34 Status Push(Stack s,Elemtype value){
if(s-&top - s-&base == s-&stackSize){
s-&base = (Elemtype*)realloc(s-&base,sizeof(Elemtype) * (STACK_INIT_SIZE + STACK_INCREMENT));
if(!s-&base)
return ERROR;
s-&top = s-&base + STACK_INIT_SIZE;
s-&stackSize = STACK_INIT_SIZE + STACK_INCREMENT;
*(s-&top) =
return OK;
46 int StackLenth(Stack s){
return s-&top - s-&base;
49 Status RPT(){
//reverse polish notation
double operater1,operater2;
int i = 0;
char bufferDigit[DIGITBUFFER];
InitStack(s);
Please Enter Reverse Polish Notation!(RPN)\n");
printf("------note:
separated by space between -------\n");
printf("------
number or operator.end of '#'-------\n");
scanf("%c", &c);
while(c != '#'){
/* 处理输入的数字：由于使用%c接受输入，所以对于123这样的多位数的
* 输入%c是不能处理的。所以设置了char型的数组bufferDigit来缓存输
* 入的多位数。在开始了多位数的输入之后，必将以空格来结束该多位数
* 输入，所以if(c == ' ')用来判断多位数的结束。以便将缓存在char
* 型数组中的多位数转化为double并且Push。
while( isdigit(c) || c == '.'){
if(i == 10){
printf("number is too lager\n");
return ERROR;
bufferDigit[i++] =
bufferDigit[i] = '\0';
scanf("%c", &c);
if(c == ' '){
//不是空格就一定还是数字
result = atof(bufferDigit);
Push(s,result);
/* 处理输入的运算符
switch(c){
Pop(s,&operater1);
Pop(s,&operater2);
Push(s,operater1 + operater2);
Pop(s,&operater1);
Pop(s,&operater2);
Push(s,operater2 - operater1);
Pop(s,&operater1);
Pop(s,&operater2);
Push(s,operater1 * operater2);
Pop(s,&operater1);
Pop(s,&operater2);
Push(s,operater2 / operater1);
scanf("%c", &c);
Pop(s,&result);
printf("The result of RPN is %f\n",result);
117 Status ShowStack(Stack s){
while(s-&base != s-&top){
printf("%f ",*(--(s-&top)));
printf("\n");
123 Status Test(){
InitStack(s1);
Push(s1,1);
Push(s1,2);
Push(s1,3);
ShowStack(s1);
131 int main(){
InitStack(s);
Push(s,1);
Push(s,2);
Push(s,3);
ShowStack(s);
142 /* 该程序编写的RPT部分功能可以完成，但是Text部分存在不解之处，在程序的124~129行的代码与134到
* 139行的代码完全相同。但是在main函数中的可以顺利运行，而在Test函数中的则出现错误(无错误提示)
* 如果将124~129行的代码改成如下则可以顺利运行：
StackNode s1;
InitStack(&s1);
Push(&s1,1);
Push(&s1,2);
Push(&s1,3);
ShowStack(&s1);
不知为何期待大牛指导。
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 1234567891011 Copyright & &&版权所有1300人阅读
编程语言（3）
要实现一个简单的计算器,可以对+,-,*,/,(,)进行处理并返回正确的值,最先想到的就是逆波兰表达式实现之.首先,用到第一个栈把算式转化为逆波兰表达式存一个数组中,在使用另一个栈对这个数组进行,判断,出栈,运算,入栈,判断……不断处理,最后的栈顶元素就是结果,直接返回就ok.关于这一个过程这篇博客写得很清楚:
下面是我用c++实现的,我已经测试了多组输入OK.
#include&iostream&
#include&stack&
#include &stdlib.h&
#include&stdio.h&
using namespace std;
int Priority(char ch)
switch(ch)
case'(':i=1;break;
case'+':i=2;break;
case'-':i=2;break;
case'*':i=4;break;
case'/':i=4;break;
case')':i=5;break;
default:i=-1;break;
void tonibolan(char *ch,char retch[100])
stack&char& st2;
while(*ch!='\0')
if(*ch&='0'&&*ch&='9')
retch[i++]=*
else if(*ch=='(')
st2.push(*ch);
else if(*ch==')')
while(st2.top()!='(')
retch[i++]=st2.top();
st2.pop();
if(st2.top()=='(')
st2.pop();
else if(st2.empty()||Priority(*ch)&Priority(st2.top()))
st2.push(*ch);
while(Priority(*ch)&=Priority(st2.top()))
retch[i++]=st2.top();
st2.pop();
if(st2.empty())
st2.push(*ch);
while(!st2.empty())
retch[i++]=st2.top();
st2.pop();
int calcval(char *ret)
stack&char&
while(*ret!='\0')
if(*ret&='0'&&*ret&='9')
st.push(*ret);
switch(*ret)
char a=st.top();
char b=st.top();
st.push(((a-'0')+(b-'0')+'0'));
char a=st.top();
char b=st.top();
st.push(((b-'0')-(a-'0'))+'0');
char a=st.top();
char b=st.top();
st.push(((b-'0')*(a-'0'))+'0');
char a=st.top();
char b=st.top();
if(a!='0')
st.push((((b-'0')/(a-'0'))+'0'));
cout&&"除数为0错误"&&
return st.top()-'0';
int main()
char ret[100]={0};
char ch[100]={0};
cin.get(ch,100);
tonibolan(ch,ret);
int len=sizeof(ret)/sizeof(0);
cout&&"算式的逆波兰表达式为："&&
while(len--)
cout&&' '&&ret[i++];
cout&&"\n算式的计算结果为："&&
cout&&calcval(ret)&&
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：2405次
排名：千里之外
(1)(3)(1)(2)(2)数据结构练习题 004 栈 逆波兰表达式的计算_C++,C语言_ThinkSAAS
数据结构练习题 004 栈 逆波兰表达式的计算
数据结构练习题 004 栈 逆波兰表达式的计算
内容来源： 网络
数据结构练习题 004 栈 表达式的计算——逆波兰用联合表达栈元素，是懒，不想写2次栈的实现代码。以空间换时间。
ExprStack.h
#ifndef EXPRSTACK_H
#define EXPRSTACK_H
#define DEFAULTSTACKSIZE
#define STACKINCREMENT
typedef union element_type_tag
} ELEMENTTYPE;
typedef struct stack_operator_tag
ELEMENTTYPE *
} STACKEXPR;
STACKEXPR *CreateStack(void);
void DestroyStack(STACKEXPR *p);
int PushElement(STACKEXPR *p, ELEMENTTYPE d);
int PopElement(STACKEXPR *p, ELEMENTTYPE *d);
int GetTopElement(STACKEXPR *p, ELEMENTTYPE *d);
ExprStack.c
#include &stdlib.h&
#include "ExprStack.h"
* 创建空栈
* 参数：无
* 返回值：栈指针
STACKEXPR *CreateStack(void)
STACKEXPR *p;
p = (STACKEXPR *)malloc(sizeof(STACKEXPR));
if(p == NULL)
return NULL;
p-&base = (ELEMENTTYPE *)malloc(sizeof(ELEMENTTYPE)*DEFAULTSTACKSIZE);
if(p-&base == NULL)
return NULL;
p-&top = 0;
p-&size = DEFAULTSTACKSIZE;
* 参数：p 栈指针
* 返回值：无
* 细节：释放栈内数据内存和栈内存
void DestroyStack(STACKEXPR *p)
if(p-&base)
free(p-&base);
* 参数：p 栈指针，d 入栈数据
* 返回值：成功返回 1，失败返回 0
* 细节：若栈满，则先增容。压数据入栈
int PushElement(STACKEXPR *p, ELEMENTTYPE d)
if(p == NULL || p-&base == NULL)
//栈满则增容
if(p-&top &= p-&size)
p-&base = (ELEMENTTYPE *)realloc(p-&base,
sizeof(ELEMENTTYPE)*(p-&size + DEFAULTSTACKSIZE));
if(p-&base == NULL)
p-&size += DEFAULTSTACKSIZE;
*(p-&base + p-&top) =
* 参数：p 栈指针，d 存放出栈数据的地址
* 返回值：成功返回 1，失败返回 0
int PopElement(STACKEXPR *p, ELEMENTTYPE *d)
if(p == NULL || p-&base == NULL || d == NULL || p-&top &= 0)
*d = *(p-&base + p-&top);
* 取栈顶元素值
* 参数：p 栈指针，d 存放栈顶数据的地址
* 返回值：成功返回 1，失败返回 0
int GetTopElement(STACKEXPR *p, ELEMENTTYPE *d)
if(p == NULL || p-&base == NULL || d == NULL || p-&top &= 0)
*d = *(p-&base + p-&top - 1);
ExprString.h
#ifndef EXPRSTRING_H
#define EXPRSTRING_H
int Infix2suffix(char *t, char *s);
int CalSuffix(char *s, double *r);
ExprString.c
#include &stdlib.h&
#include &string.h&
#include "ExprStack.h"
#include "ExprString.h"
int GetOptrLvl(char c);
int GetType(char c);
int Operate(double a, char c, double b, double *r);
* 判断字符类型
* 参数：c 字符
* 返回值：空格 5，左括号 4，右括号 3，运算符 2，数 1，其他 0
int GetType(char c)
if(c == & &)
else if(c == &(&)
else if(c == &)&)
else if(c == &+& || c == &-& || c == &*& || c == &/&)
else if((c &= &0& && c &= &9&) || c == &.&)
* 取得运算符等级
* 参数：c 字符
* 返回值：乘除 5，加减 3，左括号 1，其他 0
int GetOptrLvl(char c)
* 计算结果
* 参数：a b 操作数，c 操作符，r 计算结果
* 返回值：有效计算返回 1，无效计算返回 0
int Operate(double a, char c, double b, double *r)
if(b != 0)
//这里没有 break ，顺着 default 返回 0
* 中缀表达式转后缀表达式
* 参数：t 目标后缀表达式，s 源中缀表达式
* 返回值：成功 1，失败 0
* 细节：t 必须空间充足，后缀表达式各元素间以 空格 分割
int Infix2suffix(char *t, char *s)
STACKEXPR *p;
ELEMENTTYPE
int len, i,
if(!t || !s || (len = strlen(s)) & 1 || !(p = CreateStack()))
for(i=0; i& i++)
switch(GetType(s[i]))
//右括号：栈顶出栈，直至匹配到左括号
while(PopElement(p, &c) && c.optr != &(&)
*t++ = & &;
//操作符：+ - * /
//本操作符等级不高于栈顶操作符，出栈
while(GetTopElement(p, &c) && GetOptrLvl(s[i])&=GetOptrLvl(c.optr))
PopElement(p, &c);
*t++ = & &;
//这里没有 break，顺着直接进栈
//左括号：直接进栈
c.optr = s[i];
if(PushElement(p, c) == 0) goto ERROR;
//数字：直接进后缀表达式
*t++ = s[i++];
} while(GetType(s[i]) == 1);
// i 加多了一次，回退 1
*t++ = & &;
//空格：忽略
//非法字符
goto ERROR;
//栈内剩余操作符全部出栈
while(PopElement(p, &c))
if(c.optr == &(&) goto ERROR;
*t++ = & &;
DestroyStack(p);
DestroyStack(p);
* 计算后缀表达式的值
* 参数：s 后缀表达式， r 存放结果
* 返回值：成功 1，失败 0
int CalSuffix(char *s, double *r)
STACKEXPR *p;
ELEMENTTYPE
double a, b,
char t[256] = "";
int len, i,
if(!r || !s || (len = strlen(s)) & 1 || !(p = CreateStack()))
for(i=0; i& i++)
switch(GetType(s[i]))
//数字直接进栈
t[j++] = s[i++];
} while(GetType(s[i]) == 1);
t[j] = &&;
c.opnd = atof(t);
if(PushElement(p, c) == 0) goto ERROR;
//符号：计算
if(PopElement(p, &c) == 0) goto ERROR;
if(PopElement(p, &c) == 0) goto ERROR;
if(Operate(a, s[i], b, &ab) == 0) goto ERROR;
if(PushElement(p, c) == 0) goto ERROR;
//忽略空格
goto ERROR;
//取结果值
if(PopElement(p, &c) == 0) goto ERROR;
DestroyStack(p);
DestroyStack(p);
#include &stdio.h&
#include "ExprStack.h"
#include "ExprString.h"
int main(int argc, char *argv[])
char infix[] = "9.1+7.5*8/4-7.9*(18/3-4)+(1.5*8+1.6)/7-8.4";
//中缀表达式
char suffix[1024];
//后缀表达式
//计算结果
infix = %s", infix);
if(Infix2suffix(suffix, infix))
suffix = %s", suffix);
if(CalSuffix(suffix, &r))
result = %g
Error : CalSuffix
Error : Infix2suffix
PHP开发框架
开发工具/编程工具
服务器环境
ThinkSAAS商业授权：
ThinkSAAS为用户提供有偿个性定制开发服务
ThinkSAAS将为商业授权用户提供二次开发指导和技术支持
让ThinkSAAS更好，把建议拿来。
开发客服微信Service Unavailable