problem
 
给你一个中缀表达式，就是平常的算术式，比如这样的1+4/2*3+4
求计算结果
 
没有提交，我编几个样例把。
 【输入样例】：
 
(((1)))
(((1+1)))
1+4/2*3+4
1+4/(2*3)+4
1+120/(20*3)+1
 
【输出样例】：
 
1
2
11
5
4
 
【中缀表达式结果】
 
1.
1.1.+
1.4.2./3.*+4.+
1.4.2.3.*/+4.+
1.120.20.3.*/+1.+
 
solution
 
【中缀表达式转后缀：】
 
1）如果遇到操作数，我们就直接将其输出。
2）如果遇到操作符（包括左括号），则我们将其放入到栈中。
3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。
4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。
5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。
ps）对于两位的数字，在转为中缀的时候记得加个点，方便求值
 
【后缀表达式求值：】
 
1）遇到数字时，将数字压入堆栈
2）遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次栈顶元素 op 栈顶元素），并将结果入栈。
 
#include<bits/stdc++.h>
using namespace std;
int Youxianji(char op){
	if(op=='*'||op=='/')return 2;
	if(op=='+'||op=='-')return 1;
	if(op=='(')return 0;
}
void ToHouzhui(string str, string& ans){
	stack<char>stk;
	ans = "";
	int i =0;
	while(i<str.size()){
		if(str[i]>='0' && str[i]<='9'){
			//ans += str[i];
			int t = 0;
			while(str[i]>='0' && str[i]<='9'){
				t = t*10+str[i]-'0';
				i++;
			}
			ans += to_string(t)+".";
		}else{
			if(stk.empty()){
				stk.push(str[i]);
			}else if(str[i]=='('){
				stk.push(str[i]);
			}else if(str[i]==')'){
				while(stk.top()!='('){
					ans += stk.top();
					stk.pop();
				}
				stk.pop();
			}else{
				while(Youxianji(stk.top())>=Youxianji(str[i])){
					ans += stk.top();
					stk.pop();
					if(stk.empty())break;
				}
				stk.push(str[i]);
			}
			i++;
		}
	}
	while(stk.size()){
		ans += stk.top();
		stk.pop();
	}
}
int culate(string str){
	stack<int>stk;
	int ans = 0, i = 0;
	while(i < str.size()){
		if(str[i]>='0'&&str[i]<='9'){
			//stk.push(str[i]-'0');
			int t = 0;
			while(str[i]!='.'){
				t = t*10+str[i]-'0';
				i++;
				//cout<<t<<endl;
			}
			i++;
			//cout<<t<<endl;
			stk.push(t);
		}else{
			int a = stk.top();  stk.pop();
			int b = stk.top();  stk.pop();
			int tmp;
			if(str[i]=='+')tmp = b+a;
			if(str[i]=='-')tmp = b-a;
			if(str[i]=='*')tmp = b*a;
			if(str[i]=='/')tmp = b/a;
			stk.push(tmp);
			i++;
		}
	}
	return stk.top();
}

int main(){
	string s,t;
	while(cin>>s){
		ToHouzhui(s,t);
		//cout<<t<<endl;
		cout<<culate(t)<<endl;
	}
	return 0;
}

如题：写出中缀表达式求值的算法：
 要求：
 ①先乘除，后加减
 ②从左向后算
 ③先括号内，后括号外
 
代码实现
 
 
 
SqStack.h 此文件为封装完成栈的相关操作
 
 
#define MAXSIZE 100
/*定义顺序栈*/
typedef struct {
	int *base;  //用于栈存储的基地址 
	int *top;  //指向该基地址的栈顶指针 
	int stackSize;  //栈的大小 
}SqStackInt;
/*定义顺序栈*/
typedef struct {
	char *base;  //用于栈存储的基地址 
	char *top;  //指向该基地址的栈顶指针 
	int stackSize;  //栈的大小 
}SqStackChar;
/*初始化*/
int InitStack_Int(SqStackInt &S){
	S.base = (int *)malloc(MAXSIZE*sizeof(int));  //给基地址分配一个内存空间 
	S.top = S.base;  //将栈顶指针指向这个基地址 
	S.stackSize = MAXSIZE;  //设置栈的大小 
	return 0;
} 
int InitStack_Char(SqStackChar &S){
	S.base = (char *)malloc(MAXSIZE*sizeof(char));  //给基地址分配一个内存空间 
	S.top = S.base;  //将栈顶指针指向这个基地址 
	S.stackSize = MAXSIZE;  //设置栈的大小 
	return 0;
} 
/*进栈*/
int Push_Int(SqStackInt &S,int e){
	if(S.top-S.base==S.stackSize) return -1;
	*S.top = e;  //将输入的值压入栈中 
	S.top++;  //指针上移一个单位 
	printf("操作数%d进S1栈\n",e) ;
	return 0;
} 
int Push_Char(SqStackChar &S,char e){
	if(S.top-S.base==S.stackSize) return -1;
	*S.top = e;  //将输入的值压入栈中 
	S.top++;  //指针上移一个单位 
	printf("操作符%c进S2栈\n",e) ;
	return 0;
}
/*出栈*/
int Pop_Int(SqStackInt &S,int &e) {
	if(S.base==S.top) return -1;
	S.top--;  //指针下移一个 
	e = *S.top;  //将当前指针所指的值赋值给e 
	printf("出栈元素为:%d\n",e); 
	return 0;
}
int Pop_Char(SqStackChar &S,char &e) {
	if(S.base==S.top) return -1;
	
	S.top--;  //指针下移一个 
	e = *S.top;  //将当前指针所指的值赋值给e 
	printf("出栈符号为:%c\n",e); 
	
	return 0;
}
/*获取栈的长度*/
int GetLength_Int(SqStackInt S){
	return S.top-S.base;  
}
int GetLength_Char(SqStackChar S){
	return S.top-S.base;  
}
/*判断栈空*/ 
int StackEmpty_Int(SqStackInt S) {
	if(S.top==S.base) return 0;  //为空返回 0 
	return 1;  //不为空返回1 
} 
int StackEmpty_Char(SqStackChar S) {
	if(S.top==S.base) return 0;  //为空返回 0 
	return 1;  //不为空返回1 
} 
/*清空栈*/ 
int ClearStack_Int(SqStackInt S){
	if(S.base) //栈不为空 
	S.base = S.top;
	return 0;
} 
int ClearStack_Char(SqStackChar S){
	if(S.base) //栈不为空 
	S.base = S.top;
	return 0;
} 
/*销毁栈*/ 
int DestroyStack_Int(SqStackInt &S){
	if(S.base){
	free(S.base);
	S.stackSize = 0;
	S.top = S.base = NULL; 
	}
	return 0;
}
int DestroyStack_Char(SqStackChar &S){
	if(S.base){
	free(S.base);
	S.stackSize = 0;
	S.top = S.base = NULL; 
	}
	return 0;
}
/*读取栈顶元素*/
int GetTop_Int(SqStackInt S) {
	return *(S.top-1); 
}
char GetTop_Char(SqStackChar S) {
	return *(S.top-1); 
}

 
 
 
EvaluateExpression.cpp
 
 
#include<stdio.h>
#include<stdlib.h> 
#include"sqStack.h"

int isOper(char c){
	if(c == '#' || c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'){
		return 1; //是操作符 
	}else{
		return 0;  //不是操作符 
	}
}
/*
* c1:栈顶操作符
* c2:扫描操作符 
*
*/
char getStackTopPriority(char StackTop,char c){
	//printf("Priority:%c::%c\n",StackTop,c);
	if(StackTop == '#' || (StackTop == '(' && c != ')') || c == '(' ||( (StackTop == '+' || StackTop == '-')&&((c == '*' || StackTop == '*')))) {
		return '<';  //栈顶操作符优先级 小于等于 当前扫描操作符则  操作符进栈 
	}else if(StackTop =='(' && c == ')'){
		return '=';
	}else if(c == '*' || c == '/'||c == ')'){
		return '>' ;
	}else{
		return '>';
	}
	
}
/*
*从S1栈中弹出两个操作数 a和b 
*从S2栈中弹出一个操作符  oper 
* 然后两个操作数和一个操作符进行运算 
*/
int operate(int a,char oper,int b){
	if(oper == '+'){
		return a+b;
	}else if(oper=='-'){
		return a-b; 
	}else if(oper == '*'){
		return a*b;
	}else {
		return a/b;
	}
}
main(){
	char arr[] = {'2','+','4','*','5','*','(','2','+','3',')','#'};
	puts(arr);
	SqStackInt S1;  //用来存储操作数的栈 int 类型 
	SqStackChar S2;
	//初始化两个栈 
	InitStack_Int(S1); 
	InitStack_Char(S2);
	//操作符栈 进栈一个 # 号作为结束标志 
	Push_Char(S2,'#');
	int i = 0;  //用于循环遍历 中缀表达式 arr 数组 
	while(arr[i]!='#'||GetTop_Char(S2)!='#'){
	
		if(!isOper(arr[i])){  //如果不是操作符 
			int e = arr[i] - '0';
			Push_Int(S1,e);  //进操作数 S1 栈 
			i++;
		}else{ 				//是操作符等待进入 S2 栈 
				char e = arr[i]; 
				//比较操作符 S2栈  当前栈顶操作符的和当前扫描到的操作符优先级大小 
				switch (getStackTopPriority(GetTop_Char(S2),e)){  
					
				case '<':{  //栈顶操作符优先级小--> 
					Push_Char(S2,e); 
					i++;
					break;
				}
					
				case '=' :{
					char x;
					Pop_Char(S2,x);
					i++;
					break;
				}
				
				case '>' :{
					int a,b;char oper;
					Pop_Int(S1,b);Pop_Int(S1,a);
					Pop_Char(S2,oper);
					int e = operate(a,oper,b);
					Push_Int(S1,e);
					
					break;
				}
			} 			
		} 
	}

	
	printf("运算结果为：%d",GetTop_Int(S1));
	

}
 
运行结果
 

一、思路
 
有些类似于先把中缀表达式转化为后缀表达式，然后再对后缀表达式求值。但是因为我们最终只需要求出来的值，不想得到后缀表达式，所以就一边遍历一边计算了。关键点在于，我们借助两个栈，一个栈存放操作数，一个栈存放运算符。每次计算都是从运算符栈弹出一个运算符，从操作数栈弹出两个操作数，计算后的结果压回操作数栈。
 
二、代码实现
 
def infix_evaluator(infix_expression : str) -> int :
    '''这是中缀表达式求值的函数
    :参数 infix_expression:中缀表达式
    '''
    token_list = infix_expression.split()
    print(token_list)
    # 运算符优先级字典
    pre_dict = {'*':3,'/':3,'+':2,'-':2,'(':1}
    # 运算符栈
    operator_stack = []
    # 操作数栈
    operand_stack = []
    for token in token_list:
        # 数字进操作数栈
        if token.isdecimal() or token[1:].isdecimal():
            operand_stack.append(int(token))
        # 左括号进运算符栈
        elif token == '(':
            operator_stack.append(token)
        # 碰到右括号，就要把栈顶的左括号上面的运算符都弹出求值
        elif token == ')':
            top = operator_stack.pop()
            while top != '(':
                # 每弹出一个运算符，就要弹出两个操作数来求值
                # 注意弹出操作数的顺序是反着的，先弹出的数是op2
                op2 = operand_stack.pop()
                op1 = operand_stack.pop()
                # 求出的值要压回操作数栈
                # 这里用到的函数get_value在下面有定义
                operand_stack.append(get_value(top,op1,op2))
                # 弹出下一个栈顶运算符
                top = operator_stack.pop()
        # 碰到运算符，就要把栈顶优先级不低于它的都弹出求值
        elif token in '+-*/':
            while operator_stack and pre_dict[operator_stack[-1]] >= pre_dict[token]:
                top = operator_stack.pop()
                op2 = operand_stack.pop()
                op1 = operand_stack.pop()
                operand_stack.append(get_value(top,op1,op2))
            # 别忘了最后让当前运算符进栈
            operator_stack.append(token)
    # 表达式遍历完成后，栈里剩下的操作符也都要求值   
    while operator_stack:
        top = operator_stack.pop()
        op2 = operand_stack.pop()
        op1 = operand_stack.pop()
        operand_stack.append(get_value(top,op1,op2))
    # 最后栈里只剩下一个数字，这个数字就是整个表达式最终的结果
    return operand_stack[0]

def get_value(operator : str, op1 : int, op2 : int):
    '''这是四则运算函数
    :参数 operator:运算符
    :参数 op1:左边的操作数
    :参数 op2:右边的操作数
    '''
    if operator == '+':
        return op1 + op2
    elif operator == '-':
        return op1 - op2
    elif operator == '*':
        return op1 * op2
    elif operator == '/':
        return op1 / op2

# 用一个例子试试，得出了结果  -10
print(infix_evaluator('-5 * 1 - ( 2 + 3 )'))
 
 
 
如果这篇博文帮到了你，就请给我点个赞吧(#^.^#)
 
有疑问也欢迎留言~博主可nice啦，在线秒回ヾ(◍°∇°◍)ﾉﾞ

/*
	中缀表达式求值也就是
	1、中缀表达式转后缀表达式
	2、后缀表达式求值
	合并 
*/
#include<stdlib.h>
#include<stdio.h>
#define Maxsize 10
typedef struct node{
	char data[Maxsize];
	int top;
}Stack;
bool Isempty(Stack &s){
	if(s.top == -1){
		return true;
	}
	return false;
}
bool IsFull(Stack &s){
	if(s.top+1 == Maxsize){
		return true;
	}
	return false;
}
void InitStack(Stack &s){
	s.top = -1;
}
bool PushStack(Stack &s,char data){
	if(IsFull(s)){
		return false;
	}
	s.data[++s.top] = data;
	return true;
}
bool PopStack(Stack &s,char &data){
	if(Isempty(s)){
		return false;
	}
	data = s.data[s.top--];
	return true;
}
bool GetTop(Stack &s,char &data){
	if(Isempty(s)){
		return false;
	}
	data = s.data[s.top];
	return true;
}
int length(char str[]){
	int length=0;
	while(str[length] != '\0'){
		length++;
	}
	return length;
}
bool IsNumber(char a){
	if(a >= '0' && a <= '9'){
		return true;
	}
	return false;
}
void change(Stack &s,char str[],char last[]){
	int len = length(str);
	int flag = -1;
	char data;
	for(int i=0;i<len;i++){
		/*
			如果是数字，直接拿出来，不做任何处理 
		*/
		if(IsNumber(str[i])){
			flag++;
			last[flag] = str[i];
		}
		/*
			加减运算符优先级最低，如果栈顶元素为空则直接入栈，否则将栈中存储的运算符全部弹栈，
			如果遇到左括号则停止，将弹出的左括号从新压栈，因为左括号要和又括号匹配时弹出，
			这个后面单独讨论。弹出后将优先级低的运算符压入栈中
		*/
		else if(str[i] == '+' || str[i] == '-'){
			if(Isempty(s)){
				PushStack(s,str[i]);
			}else{
				while(!Isempty(s) && s.data[s.top] != '('){
					PopStack(s,data);
					flag++;
					last[flag] = data;	
				}
				PushStack(s,str[i]);
			}
		}
		/*
			乘、除、左括号都是优先级高的，直接压栈
		*/
		else if(str[i] == '(' || str[i] == '*' || str[i] == '/'){
			PushStack(s,str[i]);
		}
		/*
			当遇到右括号是，把括号里剩余的运算符弹出，直到匹配到左括号为止
 			左括号只弹出不打印（右括号也不压栈）
		*/
		else if(str[i] == ')'){
			PopStack(s,data);
			while(data != '(' ){
				flag++;			
				last[flag] = data; 
				PopStack(s,data);
			}
		}
	}
	/*
		最后把栈中剩余的运算符依次弹栈
	*/
	while(!Isempty(s)){
		PopStack(s,data);
		flag++;			
		last[flag] = data; 
	}
	last[++flag] = '\0';
}

bool lastnum(Stack &s,char str[],char &data){
	int len = length(str);
	char a,b,c;
	int x,y ;
	for(int i = 0;i<len;i++){
		if(IsNumber(str[i])){
			PushStack(s,str[i]);	
		}
		else{
			PopStack(s,b);
			PopStack(s,a);
			if(str[i] == '+'){
				x = a - '0';
				y = b - '0';
				x = x + y;
			}else if(str[i] == '-'){
				x = a - '0';
				y = b - '0';
				x = x - y;
			}else if(str[i] == '*'){
				x = a - '0';
				y = b - '0';
				x = x * y;
			}else if(str[i] == '/'){
				x = a - '0';
				y = b - '0';
				x = x / y;
			}
			c = x + 48;
			PushStack(s,c); 
		}
	}
	PopStack(s,data);
}



int main(){
	Stack s;
	InitStack(s);
	char data; 
	char str[] = "2*(9+6/3-5)+4";
	int len = length(str);
	char last[] ="";
	change(s,str,last);
	lastnum(s,last,data);
	int zdk = data - '0';
	printf("%d",zdk);
}