中缀算式基于栈的中缀算式表达式求值（双栈实现） 千次阅读

2019-05-17 23:07:40

问题描述：输入一个中缀表达式，求解表达式的值。参加运算的数为double类型且为正数。

输入：对于一个算术表达式，每一个表达式均以“=”结尾。当表达式只有一个“=”时，输入结束。当表达式只有一个“=”时，输入结束。参加运算的数位double类型。

输出要求：对于每组数据输出一行，为表达式运算结果。输出保留两位小数。

输入样例

2+2=

20*（4.5-3）=

输出样例：

4.00

30.00

atof的用法：

atof():double atof(const char *str );

功能：把字符串转换成浮点数

str：要转换的字符串。

返回值：每个函数返回 double 值，此值由将输入字符作为数字解析而生成。如果该输入无法转换为该类型的值，则返回值为 0.0。

函数说明：atof()会扫描参数str字符串，跳过前面的空格字符，直到遇上数字或正负符号才开始做转换，而再遇到非数字或字符串结束时('\0')才结束转换，并将结果返回，str字符串可包含正负号、小数点或E(e)来表示指数部分。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<stack>
using namespace std;
int cmp(char c)
{
	if(c=='=')         return 0;
	if(c=='-'||c=='+') return 1;
	if(c=='*'||c=='/') return 2;
	return 0;
} 
void compute(stack<double>&num,stack<char>&op)
{
	double b=num.top();
	num.pop();
	double a=num.top();
	num.pop();
	switch(op.top())
	{
		case'+':num.push(a+b);break;
		case'-':num.push(a-b);break;
		case'*':num.push(a*b);break;
		case'/':num.push(a/b);break;
	}
	op.pop();
}
int main()
{
	string c;
	stack<double> num;
	stack<char> op;
	while(cin>>c)
	{
		if(c=="=") break;
	    int len=c.length();
	    for(int i=0;i<len;i++)
	    {
			if(isdigit(c[i]))
			{
				double number=atof(&c[i]); 
				while( i<len && (isdigit(c[i])||c[i]=='.') )  i++;
				i--;               //一定要回到当前字符 
				num.push(number);
			}
			else 
			{
				if(c[i]=='(')       //左括号直接入栈 
				{       
					op.push(c[i]);
				}
				else if(c[i]==')')  //右括号 出栈计算直到左括号为止 
				{   
					while(op.top()!='(') compute(num,op);
					op.pop();
				}
				else if(op.empty()||cmp(c[i])>cmp(op.top()))  //栈空或者当前字符比栈顶字符优先级要高 ，直接入栈 
				{
					op.push(c[i]);
				}
				else //当前字符比栈顶字符优先级要低或者级别相同，那就出栈计算
				{ 
					while(!op.empty()&&cmp(c[i])<=cmp(op.top())) compute(num,op);
					op.push(c[i]);
				}
			}
	    }
	    op.pop();
	    printf("%.2f\n",num.top());
	    num.pop();
    } 
	return 0;
}

更多相关内容

中缀算式转后缀算式

千次阅读 2014-10-30 11:15:17

#include #include #include #ifndef _Stack_h struct StackRecord; typedef struct StackRecord *Stack; int IsEmpty(Stack s); int IsFull(Stack s);...Stack CreateStack(int MaxElements);...void DisposeStack(St

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#ifndef _Stack_h

struct StackRecord;
typedef struct StackRecord *Stack;

int IsEmpty(Stack s);
int IsFull(Stack s);
Stack CreateStack(int MaxElements);
void DisposeStack(Stack s);
void MakeEmpty(Stack s);
void Push(int x,Stack s);
int Top(Stack s);
void Pop(Stack s);
int TopAndPop(Stack s);
#endif 
//head is dummy

#define EmptyTOS -1
#define MinStackSize 5

struct StackRecord{
	int capacity;
	int topofstack;
	int *a;
}; 

int IsEmpty(Stack s){
	return s->topofstack == EmptyTOS;
}

int IsFull(Stack s){
	return s->topofstack == s->capacity -1;
}

Stack CreateStack(int MaxElements){
Stack s;/*
if(MaxElements<MinStackSize){
	printf("Stack size is too small\n");
	return 0;
}	
*/
s = (Stack)malloc(sizeof(struct StackRecord));
if(s == NULL){
	printf("Out of Space!\n");
	return 0;
}
s->a = (int *)malloc(sizeof(int)*MaxElements);
if(s->a == NULL){
	printf("Out of Space\n");
	return 0;
}
s->capacity = MaxElements;
MakeEmpty(s);
return s;
}

void DisposeStack(Stack s){
	if(s!= NULL){
		free(s->a);
		free(s);
	}
}

void MakeEmpty(Stack s){
	s->topofstack = EmptyTOS;
}

void Push(int x,Stack s){
	if(IsFull(s))
		printf("Stack is Full\n");
	s->a[++s->topofstack] = x;
}

int Top(Stack s){
	if(!IsEmpty(s))
		return s->a[s->topofstack];
	printf("Stack is Empty\n");
	return 0;
}

void Pop(Stack s){
	if(IsEmpty(s))
		printf("Stack is Empty\n");
	else s->topofstack--;
}

int TopAndPop(Stack s){
	if(!IsEmpty(s))
		return s->a[s->topofstack--];
	printf("Stack is Empty\n");
	return 0;
}
int compare(char a,char b){
	if((a == '+'||a == '-')&&(b == '*'||b == '/'))
		return -1;
	else if((a == '*'||a == '/')&&(b == '+'||b == '-'))
		return 1;
	else if((a == '*'||a == '/')&&(b == '*'||b == '/'))
		return 0;
	else if((a == '+'||a == '-')&&(b == '+'||b == '-'))
		return 0;
	else if(b == ')'&&a !='(')
		return 1;
	else if(a == '(')
		return -1;
}
char *InfixToPostfix(char *express){
	int len,i,j;
	char postfix[50],ch;
	Stack s;
	len = strlen(express);
	s = CreateStack(len);
	for(i = 0,j;i<len;i++){
		if(express[i]>='0'&&express[i]<='9'||express[i] == '.'){
			postfix[j++] = express[i];
			if((express[i+1]<'0' ||express[i+1]>'9')&&express[i+1]!='.')
			postfix[j++] = ' ';
		}
		else {
			if(express[i] == '+'&&express[i-1]!=')'&&(i == 0||express[i-1]<'0'||express[i-1]>'9'))
			continue;
			if(express[i] == '-'&&express[i-1]!=')'&&(i == 0||express[i-1]<'0'||express[i-1]>'9')){
			postfix[j++] = express[i];
		    continue;
			}
			if(express[i] == '('||IsEmpty(s))
				Push(express[i],s);
			/* else if(express[i] == ')'){
				while(!IsEmpty(s)&&ch = top(s)&&ch!='('){
					postfix[j++] = ch;
					postfix[j++] = ' ';
					pop(s);
				}
				pop(s);
			}*/
			else 
			{
				while(!IsEmpty(s)&&(ch =Top(s))!='\0'&&compare(ch,express[i])>=0){
					Pop(s);
					postfix[j++] = ch;
					postfix[j++] = ' ';
				}
				if(ch == '('&&express[i] == ')')
					Pop(s);
				else
					Push(express[i],s);
			}
		}
	}
	while(!IsEmpty(s)){
		ch = Top(s);
		postfix[j++] = ch;
		postfix[j++] = ' ';
		Pop(s);
	}
	if(postfix[j-1] == ' ')
		postfix[j-1] = '\0';
	else postfix[j] = '\0';
	return postfix;
}
int main(){
	char express[21];
	char *postfix;
	int i,j,n;
	scanf("%s",express);
	postfix = InfixToPostfix(express);
	printf("%s",postfix);
	return 0;
}

收起

展开全文

基于栈的中缀算式表达式求值（Java实现）

2021-12-26 14:05:55

首先，项目是要实现基于栈的中缀算式表达式求值，要求循环输入一个以“=”结尾的中缀算术表达式，输出所求的表达式的值。要解决此问题，我们可以按照以下步骤来实现：建立栈，写出其基本操作创建运算符栈和操作...

一、问题分析

首先，项目是要实现基于栈的中缀算式表达式求值，要求循环输入一个以“=”结尾的中缀算术表达式，输出所求的表达式的值。
要解决此问题，我们可以按照以下步骤来实现：

建立栈，写出其基本操作
创建运算符栈和操作数栈
实现依次读取表达式中的字符，操作数入操作数栈，运算符入栈前要比较其优先级。当栈顶元素优先级小于新读取运算符的优先级，该运算符入栈；若优先级相等，则栈顶元素出栈，即去括号；当栈顶元素优先级大于新读取运算符的优先级，栈顶元素出栈，操作数依次出栈两个，与出栈的运算符进行计算之后将结果入操作数栈
最后操作数栈里的仅存的一个数就是表达式的结果

二、数据结构

1.逻辑结构

逻辑结构采用的是顺序栈

2.物理结构

static class SequenceStack<T>{
	T[] stackArray;
	int top;
	static int defaultSize=20;
	//栈的初始化 
	public SequenceStack(int n) {
		stackArray=(T[])new Object[n];
		top=-1;
	}	
	public SequenceStack() {
		this(defaultSize);
	}
	//入栈
	public void push(T x) {
		if(top==stackArray.length-1) {
		T[]p=(T[])new Object[stackArray.length*2];
		for(int i=0;i<=top;i++) {
			p[i]=stackArray[i];
		}
		stackArray=p;
		}
		stackArray[++top]=x;
	}
//出栈
public T pop() {
	if(top==-1) {
		System.out.print("栈为空，删除失败");
		return null;
	}
	T x=stackArray[top--];
	return x;
}
//获取栈顶元素
public T getTop() {
	if(top==-1) {
		System.out.print("栈为空，无法获取栈顶元素");
		return null;
	}
	return stackArray[top];
}
//判断栈是否为空
public boolean isEmpty() {
	return top==-1;
	}
}

三、算法

1.栈类SequenceStack中的算法

（1）栈的初始化

public SequenceStack(int n) {
	//强制转化初始化栈
	stackArray=(T[])new Object[n];
	top=-1; 
}
public SequenceStack() {
	//设置栈的空间的默认值
	this(defaultSize);
}

（2）入栈

public void push(T x) {
	//若栈满，增加空间令元素入栈；若栈不满，top值加一，指向最新的栈顶元素
	if(top==stackArray.length-1) {
	T[]p=(T[])new Object[stackArray.length*2];
	for(int i=0;i<=top;i++) {
		p[i]=stackArray[i];
	}
	stackArray=p;
	}
	stackArray[++top]=x;
}

（3）出栈

public T pop() {
	//若栈为空，则无法使元素出栈；若栈不为空，栈顶元素出栈，随后top值减一指向新的栈顶元素
	if(top==-1) {
	System.out.print("栈为空，删除失败");
	return null;
	}
	T x=stackArray[top--];
	return x;
}

（4）获取栈顶元素

public T getTop() {
	//若栈为空，则无法获取栈顶元素；若非空则返回top所指的元素即为栈顶元素
	if(top==-1) {
	System.out.print("栈为空，无法获取栈顶元素");
	return null;
	}
	return stackArray[top];
}

（5）判栈空操作

public boolean isEmpty() {
//若栈空，top值等于-1
	return top==-1;
}

2.主类text中的算法

（1）判定运算符优先级

public static boolean IsOperator(char c) {
//判定是否为规定的运算符
	switch(c) {
	case '=':
	case '+':
	case '-':
	case '*':
	case '/':
	case '(':
	case ')':return true;
	default:return false;
	}	
}

static char OP[][]= {
//用数组定义运算符的优先级表
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','#','E'},
{'>','>','>','>','E','>','>'},
{'<','<','<','<','<','E','#'}
};
public static int GetOperatorID(char Operator) {
//定义运算符下标，在数组中即可比较出彼此的优先级
	switch(Operator) {
	case '+':retCode=0;break;
	case '-':retCode=1;break;
	case '*':retCode=2;break;
	case '/':retCode=3;break;
	case '(':retCode=4;break;
	case ')':retCode=5;break;
	case '=':retCode=6;break;
	}
	return(retCode);
}
public static char Precede(char Operator1,char Operator2) {
//获取下标比较优先级
	int OperatorID1,OperatorID2;
	OperatorID1=GetOperatorID(Operator1);
	OperatorID2=GetOperatorID(Operator2);
	if(OperatorID1<0||OperatorID1>6||OperatorID2<0||OperatorID2>6) {
	return('E');
	}
	return(OP[OperatorID1][OperatorID2]);
}

（2）运算法则

public static double Operate(double op1,char cal,double op2) {
//运算法则	
	switch(cal) {
	case '+': return op1+op2;
	case '-': return op1-op2;
	case '*': return op1*op2;
	case '/': return op1/op2;
	default:return 0;
	}
}

（3）读取操作数和运算符分别进栈

public static double ExpEvaluation(char []exp) {
//建立操作数栈和运算符栈，依次读取表达式中的字符，操作数入操作数栈，运算符入栈前要比较其优先级。当栈顶元素优先级小于新读取运算符的优先级，该运算符入栈；若优先级相等，则栈顶元素出栈，即去括号；当栈顶元素优先级大于新读取运算符的优先级，栈顶元素出栈，操作数依次出栈两个，与出栈的运算符进行计算之后将结果入操作数栈
	SequenceStack<Character>OPTR=new SequenceStack<Character>();
	SequenceStack<Double>OPND=new SequenceStack<Double>();
	OPTR.push('=');
	while(exp[i]!='='||OPTR.getTop()!='=') {
		if(!IsOperator(exp[i])) {
			String temp="";
			while(!IsOperator(exp[i])&&i<exp.length) {
				temp+=exp[i];
				i++;
			}
			double result=Double.parseDouble(temp);
			OPND.push(result);
		}
		else {
			switch(Precede(OPTR.getTop(),exp[i])) {
			case '<':
			OPTR.push(exp[i]);
			i++;
			break;
			case '#':
			OPTR.pop();
			i++;
			break;
			case '>':
			thera=OPTR.pop();
			b=OPND.pop();
			a=OPND.pop();
			OPND.push(Operate(a,thera,b));
			break;
			}
		}
	}
	val=OPND.getTop();
	return(val);
}

全部代码

package shiyan;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class text {
	public static boolean IsOperator(char c) {
		switch(c) {
		case '=':
		case '+':
		case '-':
		case '*':
		case '/':
		case '(':
		case ')':return true;
		default:return false;
		}	
	}
	static char OP[][]= {
			{'>','>','<','<','<','>','>'},
			{'>','>','<','<','<','>','>'},
			{'>','>','>','>','<','>','>'},
			{'>','>','>','>','<','>','>'},
			{'<','<','<','<','<','#','E'},
			{'>','>','>','>','E','>','>'},
			{'<','<','<','<','<','E','#'}
	};
	public static int GetOperatorID(char Operator) {
		int retCode;
		retCode=-1;
		switch(Operator) {
		case '+':retCode=0;break;
		case '-':retCode=1;break;
		case '*':retCode=2;break;
		case '/':retCode=3;break;
		case '(':retCode=4;break;
		case ')':retCode=5;break;
		case '=':retCode=6;break;
		}
		return(retCode);
	}
	public static char Precede(char Operator1,char Operator2) {
		int OperatorID1,OperatorID2;
		OperatorID1=GetOperatorID(Operator1);
		OperatorID2=GetOperatorID(Operator2);
		if(OperatorID1<0||OperatorID1>6||OperatorID2<0||OperatorID2>6) {
			return('E');
		}
		return(OP[OperatorID1][OperatorID2]);
	}
	public static double Operate(double op1,char cal,double op2) {
		switch(cal) {
		case '+': return op1+op2;
		case '-': return op1-op2;
		case '*': return op1*op2;
		case '/': return op1/op2;
		default:return 0;
		}
	}
	static class SequenceStack<T>{
		T[] stackArray;
		int top;
		static int defaultSize=20;
		
		public SequenceStack(int n) {
			stackArray=(T[])new Object[n];
			top=-1;
		}	
		public SequenceStack() {
			this(defaultSize);
		}
		
		public void push(T x) {
			//栈满
			if(top==stackArray.length-1) {
				T[]p=(T[])new Object[stackArray.length*2];
				for(int i=0;i<=top;i++) {
					p[i]=stackArray[i];
				}
				stackArray=p;
			}
			stackArray[++top]=x;
		}
		
		public T pop() {
			if(top==-1) {
				System.out.print("栈为空，删除失败");
				return null;
			}
			T x=stackArray[top--];
			return x;
		}
		
		public T getTop() {
			if(top==-1) {
				System.out.print("栈为空，无法获取栈顶元素");
				return null;
			}
			return stackArray[top];
		}
		
		public boolean isEmpty() {
			return top==-1;
		}
		
	}
	public static double ExpEvaluation(char []exp) {
		char thera;
		int i=0;
		double b,a,val;	
		SequenceStack<Character>OPTR=new SequenceStack<Character>();
		SequenceStack<Double>OPND=new SequenceStack<Double>();
		OPTR.push('=');
		while(exp[i]!='='||OPTR.getTop()!='=') {
			if(!IsOperator(exp[i])) {
				String temp="";
				while(!IsOperator(exp[i])&&i<exp.length) {
					temp+=exp[i];
					i++;
				}
				double result=Double.parseDouble(temp);
				OPND.push(result);
			}
			else {
				switch(Precede(OPTR.getTop(),exp[i])) {
				case '<':
					OPTR.push(exp[i]);
					i++;
					break;
				case '#':
					OPTR.pop();
					i++;
					break;
				case '>':
					thera=OPTR.pop();
					b=OPND.pop();
					a=OPND.pop();
					OPND.push(Operate(a,thera,b));
					break;
				}
			}
		}
		val=OPND.getTop();
		return(val);
	}
    public static void main(String[]args) {
    	for(;;) {
    		try {
    			BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    			String s=br.readLine();
        		char[]us=s.toCharArray();
        		System.out.println(String.format("%.2f", ExpEvaluation(us)));
        	}catch(IOException e) {
        		e.printStackTrace();
        	}
    	}  	
    }
}

收起

展开全文

java 开发语言后端

【数据结构】基于栈的中缀算式表达式求值

千次阅读 多人点赞 2020-06-15 20:47:19

基于栈的中缀算式表达式求值问题：要求：运行软件调试引用函数将字符串转换成浮点数atof函数：strtod函数：memset函数判断符号优先级表代码实现：问题：输入一个中缀算术表达式，求解表达式的值。运算符包括+、-、...

问题：

输入一个中缀算术表达式，求解表达式的值。运算符包括+、-、*、/、(、)、=，参加运算的数为double类型且为正数。（要求：直接针对中缀算术表达式进行计算，不能转换为后缀或前缀表达式再进行计算，只考虑二元运算即可。）

要求：

（1）创建名为kcsj12.cpp的文件，并编写程序实现指定功能；
（2）输入：多组数据，每组数据一行，对应一个算术表达式，每个表达式均以“=”结尾。当表达式只有一个“=”时，输入结束。参加运算的数为double类型；
（3）输出：对于每组数据输出一行，为表达式的运算结果。输出保留两位小数。
输入样例和输出样例：

输入：
2+2=
20*（4.5-3）=
=
输出：
4.00
30.00

运行软件

CLion

调试

debug

引用函数

将字符串转换成浮点数

atof函数：

atof()是C 语言标准库中的一个字符串处理函数，功能是把字符串转换成浮点数，所使用的头文件为<stdlib.h>。

示例代码：

#include<stdlib.h>
#include<stdio.h>
int main()
{
double d;
char str[] = "123.456";
d=atof(str);
printf("string=%sdouble=%lf\n",str,d);
return 0;
}

strtod函数：

strtod是C语言及C++中的重要函数，功能是将字符串转换成浮点数，表头文件是#include <stdlib.h>，相关函数有atoi，atol，strtod，strtol。

示例代码：

#include<stdlib.h>
#include<stdio.h>
void main()
{
    char *endptr;
    char a[] = "12345.6789";
    char b[] = "1234.567qwer";
    char c[] = "-232.23e4";
    printf( "a=%lf\n", strtod(a,NULL) );
    printf( "b=%lf\n", strtod(b,&endptr) );
    printf( "endptr=%s\n", endptr );
    printf( "c=%lf\n", strtod(c,NULL) );
}

memset函数

memset是计算机中C/C++语言初始化函数。作用是将某一块内存中的内容全部设置为指定的值，这个函数通常为新申请的内存做初始化工作。

char chs[20];
memset(chs,'#', sizeof(char)*20);

判断符号优先级表

(1)先乘除，后加减；
(2)从左算到右；
(3)先括号内，后括号外

在这里插入图片描述

由规则(1), 先进行乘除运算，后进行加减运算，所以有 “+” < “"; “+” < “!”; "” >。
由规则(2), 运算遵循左结合性，当两个运算符相同时，先出现的运算符优先级高，所以有

“+” > “+”;
“-” > “-”;
" * " > " * ";
“/” > “/”。

由规则(3), 括号内的优先级高，＋、－、＊和I为81 时的优先性均低千 (" “但高于 " )”。表中的 “(” = “)” 表示当左右括号相遇时，括号内的运算已经完成。为了便千实现，假设每个表达式均以"#“开始，以”#" 结束。所以"#" = “#” 表示整个表达式求值完毕。")“与 “(”、＂＃”与”)" 以及"(“与”#" 之间无优先关系，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现了语法错误。在下面的讨论中，我们暂假定所输人的表达
式不会出现语法错误。

代码实现：

#include <iostream>
#include <stdlib.h>
#include <cstring>
#define MAXSIZE 100//初始分配的存储空间
#define OK 0
#define  OVERFLOW 1
#define ERROR 1
typedef char SElemType;
typedef int Status;
using namespace std;

//定义字符栈
typedef struct {
    SElemType *base;//栈底指针，始终指向栈底元素，构造之前和销毁之后base的值为NULL
    SElemType *top;//栈顶指针，始终指向栈顶元素的下一个位置
    int stackSize;//当前分配的存储容量，以元素为单位
} SqStackOPTR;

//定义数字栈
typedef struct {
    double *base;//栈底指针，始终指向栈底元素，构造之前和销毁之后base的值为NULL
    double *top;//栈顶指针，始终指向栈顶元素的下一个位置
    int stackSize;//当前分配的存储容量，以元素为单位
} SqStackOPND;

//字符栈的初始化
Status InitStack(SqStackOPTR &S) {
    S.base = new SElemType[MAXSIZE]; //分配空间
    if (!S.base) exit(OVERFLOW);//分配失败，异常退出
    S.top = S.base;
    S.stackSize = MAXSIZE;
    return OK;
}

//数字栈的初始化
Status InitStack(SqStackOPND &S) {
    S.base = new double[MAXSIZE]; //分配空间
    if (!S.base) exit(OVERFLOW);//分配失败，异常退出
    S.top = S.base;
    S.stackSize = MAXSIZE;
    return OK;
}

//字符栈入栈操作
Status Push(SqStackOPTR &S, SElemType e) {
    if (S.top - S.base == MAXSIZE) //说明栈满
        return ERROR;
    *S.top++ = e;//元素e进栈
    return OK;
}

//数字栈入栈操作
Status Push(SqStackOPND &S, double e) {
    if (S.top - S.base == MAXSIZE) //说明栈满
        return ERROR;
    *S.top++ = e;//元素e进栈
    return OK;
}

//字符栈出栈操作
SElemType Pop(SqStackOPTR &S) {
    char e;
    if (S.top == S.base) return ERROR; //栈空
    e = *--S.top;//这里其实是将栈顶的指针向下移了以为，没有真正的删除元素   用e返回其值
    return e;
}

//数字栈出栈操作
double Pop(SqStackOPND &S) {
    double e;
    if (S.top == S.base) return ERROR; //栈空
    e = *--S.top;//这里其实是将栈顶的指针向下移了以为，没有真正的删除元素   用e返回其值
    return e;
}

//取字符栈栈顶元素
SElemType GetTop(SqStackOPTR S) {
    char e;
    if (S.top == S.base) return ERROR;//栈空
    e = *(S.top - 1);//返回
    return e;
}

//取数字栈栈顶元素
double GetTop(SqStackOPND S) {
    double e;
    if (S.top == S.base) return ERROR;//栈空
    e = *(S.top - 1);//返回
    return e;
}

//判断字符的方法，判断输入的字符是数字还是运算符
//如果是数字，那么返回0，如果是运算符，返回1
Status In(SElemType e) {
    int isNumber;
    switch (e) {
        case '+':
        case '-':
        case '*':
        case '/':
        case '(':
        case ')':
        case '=':
            isNumber = 1;
            break;
        default:
            isNumber = 0;
            break;
    }
    return isNumber;

}

//定义一个判定运算符栈的栈顶元素与读入的运算符之间优先关系的函数
char Precede(SElemType top, char ch) {
/*
 * 算数四则运算遵循以下3条规则
 * （1）先乘除，后加减
 * （2）从左算到右
 * （3）先括号内，后括号外
 */
    char symbol;//定义一个字符串来接收> = <



    switch (top) {
        case '+':
        case '-':
            switch (ch) {
                case '+':
                case '-':
                case ')':
                case '=':
                    symbol = '>';
                    break;
                case '*':
                case '/':
                case '(':
                    symbol = '<';
                    break;
            }
            break;
        case '*':
        case '/':
            switch (ch) {
                case '+':
                case '-':
                case '*':
                case '/':
                case ')':
                case '=':
                    symbol = '>';
                    break;
                case '(':
                    symbol = '<';
                    break;
            }
            break;
        case '(':
            switch (ch) {
                case '+':
                case '-':
                case '*':
                case '/':
                case '(':
                    symbol = '<';
                    break;
                case ')':
                    symbol = '=';
                    break;
            }
            break;
        case ')':
            switch (ch) {
                case '+':
                case '-':
                case '*':
                case '/':
                case ')':
                case '=':
                    symbol = '>';
                    break;
            }
            break;
        case '=':
            switch (ch) {
                case '+':
                case '-':
                case '*':
                case '/':
                case '(':
                    symbol = '<';
                    break;
                case '=':
                    symbol = '=';
                    break;
            }
            break;
    }
    return symbol;
}

//定义一个二元运算的方法，来进行+ - * /
double Operate(double a, SElemType top, double b) {
    double sum = 0;
    switch (top) {
        case '+':
            sum = a + b;
            break;
        case '-':
            sum = a - b;
            break;
        case '*':
            sum = a * b;
            break;
        case '/':
            if (b != 0) sum = a / b;//如果是0怎么办
            break;
    }
    return sum;
}//20*（4.5-3）=

double EvaluateExpression(char ch) {
    //定义两个栈，分别为OPTR栈（放运算符）OPND栈（放数字）
    SqStackOPTR OPTR;//定义字符栈
    SqStackOPND OPND;//定义数字栈
    InitStack(OPTR);//初始化OPTR栈
    InitStack(OPND);//初始化OPND栈
    Push(OPTR, '=');//将表达式起始符’#‘压入OPTR栈
    char chs[20];//定义一个字符数组，来实现数字转换为字符串
  memset(chs,'#', sizeof(char)*20);//将字符数组的元素设置为‘#’

    while (ch != '=' || GetTop(OPTR) != '=') {//表达式没有扫描完毕或OPTR的栈顶元素不为“=”
        if (!In(ch)) {
            //这里应该将字符串转换为数字
            for (int i = 0; i <strlen(chs) ; i++) {
                if (chs[i]=='#' && !In(ch)){//如果数组的第i个元素不为‘#’或不为符号
                    chs[i]=ch;
                    cin>>ch;
                } else{
                    break;
                }
            }
            double d=atof(chs);//把字符串转换成浮点数 double
//            double d1=strtod(chs,NULL);//将字符串转换成浮点数
            Push(OPND,d);
            memset(chs,'#', sizeof(char)*20);//将字符数组的元素设置为‘#’
        } else {
            switch (Precede(GetTop(OPTR), ch)) {
                case '<':
                    Push(OPTR, ch);cin>>ch;
                    break;
                case '>':
                    char theta;
                    double b;
                    double a;
                    theta = Pop(OPTR);
                    b = Pop(OPND);
                    a = Pop(OPND);
                    double sum;
                    sum = Operate(a, theta, b);
                    Push(OPND,  sum);
                    break;
                case '=':
                    Pop(OPTR);
                    cin>>ch;
                    break;
            }
        }
    }
    return GetTop(OPND);
}

int main() {

    while (1) {
        char ch;
        cin >> ch;
        if (ch == '=')break;
        double res = EvaluateExpression(ch);
       printf("%.2lf",res);
    }
    return 0;
}

在这里插入图片描述

收起

展开全文

十套数据结构试题及答案1.doc
2019-06-24 15:03:32

1.通常从四个方面评价算法的质量：_ 准确性__、___高效性______、__易读性__和_____健壮性____。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示...中缀算式（3+4X）-2Y/3对应的后缀算式为_34X*+2Y*3/-_。

收起
中缀后缀表达式
2018-02-23 16:40:12

包含中缀转后缀以及后缀表达式计算（或中缀记法）是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法。与前缀表达式（例：+ 3 4）或后缀...

收起
后缀表达式变换为中缀表达式
2013-10-13 23:30:05

将由数字和四则运算符组成的后缀表达式变换为中缀表达式。输入的后缀表达式包含的运算符不超过15个。要求转换后的中缀表达式中不应出现不必要的括号。例如，整个表达式两端的括号要省略，不影响原计算顺序的括号要...

收起
后缀算法与中缀算法
2020-08-04 14:59:24

中缀算法就是日常计算中用到的类似a+b的算法表达式；运算符位于两个运算数中间的位置；后缀算法相比较中缀表达式的结构，不难推出后缀表达式的格式，就是符号位于两个运算量的后边位置，比如ab+表示的就是a+b;...

收起

算法
前缀、中缀和后缀算式
千次阅读 2015-08-20 16:14:00

.转换方法 中缀算式（3+4X）-2Y/3对应的后缀算式 34X*+2Y*3/- 乘号也应算进去转载于:https://www.cnblogs.com/fthjane/p/4745532.html

收起
【数据结构】表达式（3+4* X )-2* Y /3对应的后缀算式
2022-03-09 13:43:17

后缀算式9 2 3±10 2/-的值为A A -1 B 0 C 1 D 2 表达式（3+4* X )-2* Y /3对应的后缀算式为A A 3 4 X * + 2 Y * 3 / - B 3 4 X * 2 + Y * 3 / - C 3 4 * X 2 + Y * 3 / - D 3 4 X * 2 Y + * 3 / -

收起

数据结构
中缀与后缀表达式详解
千次阅读 2019-12-06 19:45:36

中缀表达式，就是我们日常适用的算式，主要是运算符的优先级和括号会改变优先级。我们人用中缀表达式是很方便的，但是计算机算很不方便，所以就有了后缀表达式。 2.原理与代码比如这样一个后缀表达式：ABCD-*+ ,...

收起
将中缀表达式转换为后缀表达式_C++程序
2012-12-26 23:49:12

将中缀表达式转换为后缀表达式_C++程序

收起
中缀表达式与后缀表达式的转换及后缀表达式的计算
千次阅读 多人点赞 2018-01-11 00:07:38

中缀表达式：也就是我们日常最容易见到的表达式，从左至右考虑运算符的优先原则。首先，我们以电脑的思维计算后缀表达式，这里必须用到栈的知识，栈通俗来讲就像一个桶，它里边存放的东西必须满足先进后出的...

收起

后缀表达式的计算
中缀表达式的计算
千次阅读 2020-04-01 17:33:27

中缀表达式：就是我们平时用的表达式形如：(3+54/2+2(1+1)*(2+2)) = 29 计算我们用两个栈来实现，一个栈存数字，一个栈存符号步骤遍历整个表达式，如果当前的字符是数字，就存进栈里面，如果是符号，就把栈...

收起
2015中缀表达式转化为后缀表达式（C++，附思路，注释多）
2021-10-30 17:07:20

详解如何将中缀表达式转化为后缀表达式_Dacyuan的学习笔记-CSDN博客_中缀算式怎么转化为后缀算式https://blog.csdn.net/Coder_Dacyuan/article/details/79941743中缀表达式转换为后缀表达式___七把刀_...

收起

c++ 数据结构链栈
中缀表达式转后缀并求解计算
2021-01-24 15:12:23

中缀表达式转换为后缀表达式具体步骤如下: 初始化两个栈：运算符栈s1和储存中间结果的栈s2；从左至右扫描中缀表达式；遇到操作数时，将其压s2；遇到运算符时，比较其与s1栈顶运算符的优先级： 4.1 如果s1为空，...

收起

数据结构 java
中缀表达式计算、后缀表达式计算、中缀转后缀
2020-03-21 08:49:14

C语言：中缀表达式计算求值、后缀表达式计算求值、中缀表达式转后缀表达式

收起

指针 c++ 数据结构

中缀算式转后缀算式

基于栈的中缀算式表达式求值（Java实现）

目录

一、问题分析

二、数据结构

1.逻辑结构

2.物理结构

三、算法

1.栈类SequenceStack中的算法

（1）栈的初始化

（2）入栈

（3）出栈

（4）获取栈顶元素

（5）判栈空操作

2.主类text中的算法

（1）判定运算符优先级

（2）运算法则

（3）读取操作数和运算符分别进栈

全部代码

【数据结构】基于栈的中缀算式表达式求值

基于栈的中缀算式表达式求值

问题：

要求：

运行软件

调试

引用函数

将字符串转换成浮点数

atof函数：

strtod函数：

memset函数

判断符号优先级表

代码实现：

十套数据结构试题及答案1.doc

中缀后缀表达式

后缀表达式变换为中缀表达式

后缀算法与中缀算法

前缀、中缀和后缀算式

【数据结构】表达式（3+4* X )-2* Y /3对应的后缀算式

中缀与后缀表达式详解

将中缀表达式转换为后缀表达式_C++程序

中缀表达式与后缀表达式的转换及后缀表达式的计算

中缀表达式的计算

2015中缀表达式转化为后缀表达式（C++，附思路，注释多）

中缀表达式转后缀并求解计算

中缀表达式计算、后缀表达式计算、中缀转后缀

中缀算式